Recommended package size and type for a surface mount linear regulator IC that will be hand-soldered?
My preference for higher power is a DPAK.  Second to that is a SOT-223.  These both have tabs that will transfer a lot of heat.  Unless it is 50mA or less, don't bother with packages that only attach to the board with pins / legs.  These things tend to heat up like crazy; they don't dissipate much power at all.

Also, don't forget to give a good copper area on top.  Additionally, you can do a pad on the bottom and attach with several vias, but the one on the component side will be most important.

For hand soldering packages like this with significant thermal mass, nothing beats a hot-air gun.  A metcal with a big spade tip is also great, but the hot air gun will save your bacon many times over.  They can be had on ebay for $300 or so.