The timing belt is best done simultaneously with the water pump. You'll save a good amount on labor doing both at once because of where theyre situated. I almost bought a used J this past spring, and the quote was a little over $700 at a local Firestone service center. I did not check with the dealer.
If the shop you choose to have the service done at allows you to bring your own parts, place your order with everythinginfiniti.com to save some money.
As driverdriver said, the J30 transmission tends to go out a bit soon in warm climates. Even in milder climates, you may run into problems later on without proper cooling (by adding an external transmission cooler) and proper fluid maintenance (annual or biannual flushes). What I'm saying is, dont consider flushing -- go ahead and do it.

Drop the pan and change the filter while youre at it, and have a cooler installed (part is $40-$60, labor is about an hour or two).
-Jesda