Nitrox or Rescue? That's a no brainer for a new diver. One will increase your bottom time (if no deco-limits are your issue), whilst the other will make you a better diver... All the usual caveats apply (crap instructor, crap course, but that goes for both).
When I am asked about Enriched Air I always ask the divers where are they planning to dive and how are they planning to dive. If you're planning on diving with a dive operator in a group of divers, and on a schedule of 2-3 dives per day when you're on vacation... save your money and don't bother with Nitrox! Most dive operations cater for a lowest common denominator in a group or have a schedule. So whilst with a good blend you might be able to get a bottom time of 3 hours, you won't actually have the time or the gas. If you're planning on doing livaboards/trips with much more diving, then hell yeah - hit that Nitrox as you'll feel the benefit in the shorter surface intervals and be less fatigued.
Rescue diver is my favourite course to teach! You're able to have so much fun with the students and the DM's and really push hard. In my view Rescue is a course that should be completed by every diver! Open Water is great, it gets you focused on you. Your air, your mask, your safety. Advanced gets you focused on you in your environment (night/deep etc) or you and equipment (photography, S&R etc). Rescue is the first course you'll encounter which starts to get you to focus on others. Completing the course with an instructor who loves teaching rescue, and you will become a much safer and more aware diver.