From your list, I would start with exhaust followed by gears. That way when you get gears, your car will sound good and you wont mind hitting higher RPM's. As for what type of exhaust, that depends on what you like. The Magnaflow catback is nice, I had it on my 02' GT myself. But it all depends on what other exhaust mods you plan on doing. If you are just swapping out your catback, then I would look at the Magnapacks instead - as the Magnaflow catback will sound very close to stock with the stock midpipe. But again that depends on what type of sound you are looking for. If you just want a little extra tone, and a deeper exhaust note then the Magnaflow catback would suit those needs. I had it paired with my stock midpipe and it gives off a nice deep note. I've also had that catback paired with LT's and an O/R H and that sound was heavenly, haha. So again it depends on what other exhaust modifications you plan on doing.
Once you have your exhaust the way you like it, then i would jump into some gears. The exhaust is a good starting point as it is something you can install yourself and save money. Gears are more involved and will cost a good chunk of change to have installed professionally. I have 4.10's on my car as well and am very happy with them. From what I had read all the time, I thought I would not be able to use first gear and would be shifting like crazy most of the time. But for normal daily driving I use first gear all the time with no problem, as long as you're not heavy on the gas - it feels similar to stock (until you get on it).
Those are two good mods to begin with: the exhaust you will hear, and the gears you will feel! Other small mods you will not notice as much, such as a CAI - but they look good under the hood, haha.