A short, general list of things that do require a tune...
Any modification to the MAF sensor. Replacement with a stock, unmodified part not included.
A differential gear change more than two steps in any direction (e.g. 3.27 to 4.10)
Changes to combustion [chamber] characteristics (e.g. PI or TFS heads, compression changes, radical cam swaps that induce dynamic compression changes) that require spark adjustments
Modifications to the fuel delivery system that affects flow rate (injector size, pressure)
Things that don't require a tune (but are often be better taken advantage of with)...
Drivetrain modifications such as the J-mod, higher stall converters, gear changes (of any size)
A higher volume fuel pump
Mild changes to intake or cams (e.g. PI intake or PI cams)
Exhaust system modifications (headers, duals, crossover pipes etc.)
Thermostat adjustment (e.g. from 195 to 180)
None of this is exhaustive, but hopefully it gives you a good idea.
For mail order tunes, Don LaSota is the one I think of. He wrote most of the in-program descriptions of the SCT PRP back in the day, and has written several tuning manuals. He is incredibly knowledgeable - and has a good way of breaking down what seems like a complicated task into simple steps.