To begin with, the term "tune-up" is kind of out of date; that is a term used to describe a maintenance service that was done on older cars and really is not used any more. On older cars, every mechanic had a different opinion of what was included in a tune-up service, but typically it included replacing spark plugs, air filter, fuel filter, distributor cap and rotor, ignition points, adjusting ignition point dwell and timing, and cleaning and adjusting the carburetor.
On newer engines there are no adjustments possible at all, since the computer controls everything. On yours though it is possible to adjust ignition base timing, although it should never need to be done unless the engine has been disassembled or the timing chain is badly worn enough to change the sync of the distributor. If the distributor has not been rotated, checking ignition timing is not likely to have any effect on the problem you are having.
Replacing spark plugs in this engine is not easy, as you have noticed. According to my flat rate guide, it takes an experienced mechanic 1.3 hours to change the plugs, which in most shops is somewhere around $100 or so in labor depending on their hourly labor rate. If you specifically requested that the shop check your timing, they should have done so, but you do not indicate whether or not you were charged for that particular service.
From the description you have, it would appear that the spark plugs are not what is causing the rough running condition youa re experiencing. You may want to take the car to a different shop, if you do not have a good working relationship with your current one or do not trust them.
Most mechanics would want to begin with a compression test on an engine this age, to make sure there are no leaking valves or other mechanical problems before moving on to other areas. Next would be a scope check of the ignition system; this test will show any ignition misfires, vacuum leaks, or fuel problems as these things change the scope pattern in different ways.
ASlso, checking to make sure the EGR valve is not stuck open at idle is something that should be done during the diagnostic process.
If your "check engine" light is on, that indicates there are diagnostic fault codes stored in computer memory that may be useful in diagnosing the cause of the problem.