I am a total newbie, so please, just take this for what it is worth, which may not be much. I started out diving on air. I was totally bone tired exhausted when I finished my dives. Since I got NITROX certified and have started using NITROX, I feel so energized after my dives. Once again, it could just be that I'm diving better, and it could all be in my head, but darn, I sure feel great after diving, and it seems like this feeling came when I started NITROX. (please don't flame me if I'm way off, but if I'm giving incorrect thoughts, don't hesitate to let me know.)
Lots of good information in this thread, especially referring back to the basics like slow ascents, hydration, etc, but I have to agree with Fly Girl here.
Although I think it depends on your metabolism and build - I have a large frame and very large lung capacity, which I expect makes me prone to CO2 retention problems. Nitrox has been very helpful and what I have found even more helpful, since I acquired the requisite training, has been the use of a fairly hot deco mixture.
In fact, I've gone from dragging myself back onto the boat and lying down in an attempt to avoid seasickness - to leaping back onto the boat with an exclamation of, "Ok, what's the soup today?" Not even exaggerating.
YMMV