Holy cans of worms batman
The main question is what are your goals for the car? What body style do YOU like? 64-66 has a smaller engine compartment, a 351 will be the largest that will fit in a stock compartment and will have a few clearance issues (spark plugs will be accessable but a little tough, headers, etc). Since you mention power and speed then I assume it will not be a stock inline 6. You want to look for a car that was originally a V8 car. If you purchase a 6cyl car and want to put a V8 into it then most of the front suspension will need to be replaced with V8 parts.
What you will end up spending is entirely up to you. How much of the work can you do yourself? That will be a major factor. It will ALWAYS cost more than you expect it to, I guarantee it.
The best engine for power and speed.....this is a little too open but Ill take a stab at it. You can build a nice budget 302 with some ported 351 heads, a decent intake and 4 barrel carb, 4 or 5 speed, and some 3.55 gears that will be a fun cruiser. This is assuming a moderate budget, sure you can build a 351 with a cam, forged bottom end, aluminum heads, intake, carb and a supercharger/turbo.
Any way to fix rust? Sure, cut it out and replace the sheet metal. How good are you with a welder? Got a buddy who can weld? On a 64-66 at least: pour a cup of water in the cowl and see if it ends up on the floor where your feet would be, the cowl is a good indicator of how much rust you may find elsewhere. Check the wheel wells, under side of the doors and undercarridge. Check for bubbles in the paint, that means that there is rust under the paint.
I pretty much scratched the surface here but they are difficult questions to answer. What is the best to restore? I vote for 64-66. How much will you spend? Totally up to you. Best engine? A matter of opinion but a million options available to you for any price range. Parts attainable? Most of the parts can be purchased from NPD, California
Mustang, etc, etc, etc or found in a junk yard.
The main thing that I see discourage people is rust. They purchase a car that has more rust than they thought it had. Take someone with you to look for your project, hopefully someone who knows that specific years quirks. Have fun with it, good luck