Ok....so you bought it that way......well I'm at least glad to hear you didn't waste your money on the stud job, but then again I suppose at this point it's not really a waste since they're not leaking, but either way YES, the heads should have been milled flat. A very flat, very clean surface is the key to a long lasting, high HP handling head job.....that's engine building 101.
A shop will charge anywhere from $3500-$7500 on a head and stud job depending on:
What parts still may need updated (shouldn't need any if it all was done at the last job but who knows)
What parts can be re-used (the studs can be re-used a couple times IF they weren't overtorqued)
Condition of heads upon removal (sometimes they crack)
Machining costs
Their shop rate
Also, IMO, since you're starting to scratch the "I want more power" itch, you may also look into having the heads o-ringed. It's not 100% necessary for your goals now, but it's extra insurance later should you want to build up more without tearing into it again.
Given that you bought the truck that way I'd be curious if it was geared already so my initial recommendation may be off depending on what the PO did. Like Thurston said above, your optimal gear ratio is going to depend on how you use your truck. How often and how heavy do you tow vs. how fast do you want to go vs. how hard do you want to work the truck. Do you find yourself cruising at 70-80mph normally? Do you tow often, but pretty light (sub 10k lbs?), or heavy? Gear ratios just determine the RPM the engine will be at, at a specific speed.......For a truck with 37s that tows occasionally, but is mainly a DD and weekend warrior, I'd be looking at either a 4.10 option or a 4.30 at max......4.56 is a little to low for my taste.
BTW Fish, you're pretty "on", looks like the OP is in Connecticut.
