$600 for a timing belt/balance shaft belt, tensioner and water pump, on that engine, that's a tad high IMO especially considering that they're using aftermarket parts.  We can do that service for like $500, if I remember right, with OEM parts.  Call around to Mitsubishi dealers in the area, they/we were/are on a promo this past summer, menu pricing timing belt services for like $199.99 without the water pump and tensioner.  

Although on the first timing belt service (60K miles or so), I usually leave the water pump and tensioner alone, and recommend it at the second service.  The water pump on that engine is not driven by the timing belt, it is under the timing cover however they don't really leak or fail at such a low mileage.  Same with the tensioner.  At 75K miles, I'd do just the timing belt and balance shaft belt if I were working on it, and inspect the tensioner and water pump while it's apart and recommend/replace as necessary.

The cooling system flush, let your judgment be your guide there.  With the change in the seasons coming in, I'd drain/fill it personally.  There shouldn't be any need to use any cleaners or flushes at this mileage if everything else is in proper working order.

Avoid the "fuel system cleaners" and such, fuels nowadays really have all the cleaners and such in them you need.  At 70K+ miles, I'd pull the plugs and inspect them, and replace as needed.  That's about it for a tune up.  Oh, and a PCV valve.

Brake fluid is hygroscopic, it absorbs moisture, and over time this lowers the fluid's boiling point, resulting in a mushy, shitty feeling pedal.  I can understand the reasoning behind recommending that, but FWIW, I haven't flushed the brake fluid once in my F150 in five years and 90,000 miles.  I really should flush mine, but my brakes feel and stop fine right now.  Your call on that one, my personal experience on both sides of the fence sees no real error with doing it or not at this point.

For plugs, I know the Firestones around here use Bosch Platinums.  That's a no-go in most everything I've worked on, I'd recommend using the OEM NGK or Denso plug for best results.

Tires, alignment, I second the Tire Rack and an indy store.  The Tire Rack is good peoples, they'll take good care of you.

The transmission service, I've seen some torque converter shudder when using anything other than Mitsubishi's SP3 transmission fluid.  If you're gonna do the transmission, I'd strongly recommend using SP3.  It's something like $7/quart list price at a dealer, which works out to about 15 dollars more than what Firestone is charging you for their fluid.

I'd call your local Mitsubishi dealer and comparison shop them.  Our reps are pushing discounting and price matching, so they may be able to beat that price quoted.  I know the outfit I work for can (or would), because frankly, we need the work.  

For comparison's sake, when I get into work tomorrow, I'll take their estimate, punch it into our system and give you a quote for doing all those services at a Mitsubishi dealer, if you'd like.

It's one of those "I've been meaning to do it..." things I keep pushing aside in the name of other people's cars.  Honest.  I swear!

I've got knock sensors and intake gaskets that need to go on my truck, critters chewed through the bank 1 sensor harness about a year ago and I haven't tended to it yet.  I just clear the code whenever the harness flexes in just the right spot to turn the MIL on.

The mechanic's ride is always the last one to get worked on, it seems.

Arfcom makes experts out of any and every one, regardless of who they are or what they do.

So you own your own shop and made a career out of working on race cars, street cars, hell, most anything with four wheels and an engine?  Pfft, you don't know shit, I do this stuff in my front yard!

So you're a Marine officer, stationed in Afghanistan, pfft, you don't know shit, this and that is what we *should* do to win the war!

So you're a police officer, pfft, you don't know shit, that's why all you guys are crooked jack booted thugs who rape, rob and pillage behind a badge, this is how you should do your job!

And so on, and so on.

The ignorance of the particular car we're talking about here has shined through a few times, dudes who are like:

"The water pump is driven by the timing belt" (on that particular engine, it is not, but it is under the timing cover)

Or "brake fluid flushing, that's bullshit, it stopped when you got there, right?!" (even though brake fluid is hygroscopic, meaning it'll absorb moisture, even just sitting there in the master cylinder.  Someone asked why brake fluid changes color.  It's because it's hygroscopic.  It absorbs moisture in the air, moisture that also contains microscopic dirt particles, which over time changes the fluid's color from amber or clear to black.  The fluid boiling doesn't change it's color.  In fact, under normal operating conditions, the brake fluid had better not boil.  Ever.  Boiling brake fluid = no brakes.  Saying brake fluid flushing is bullshit is like saying oil changes are bullshit.  Brake fluid does wear out.)

Or "fuel system services are bullshit, just dump some stuff in the tank and replace the fuel filter" (when that particular car does not have an externally serviceable fuel filter)

Or "don't flush the transmission, it'll blow up!" (when over the course of 13 years, I've had maybe two automatic transmissions die after flushing, and as I recall, they were on borrowed time before the service anyways), or "just drop the pan and replace the filter" (when that transmission does not have an internal filter or a trans pan like most conventional automatic transmissions)

Or "Iridium spark plugs can go 100K+ miles, welcome to the 21st century" (when yes, they can make the engine physically start, idle and run past 100K miles, but no, they won't really do it well, they do wear out before 100K miles)

Or "all that stuff is WAY overpriced!" (which is humorously ironic coming from folks who claim to be conservative/pro-capitalism/anti-Obama...)

But hey, everyone is an expert on everything on Arfcom.  Except the people who actually are experts in their particular field.  Those guys, they don't know shit.