If you are going to drop the $$ for a OS don't get xp, vista is going to be required sooner or later. Might as well jump on the bandwagon now. The problem with incompatibility is becoming less common and any games worth playing from here on out will be compatible with Vista.
Basic is well... basic, doesn't have some of the fancy window stacking features and the biggest difference is it doesn't have the full media center integrated.
Preimium has the full media center and the fancy window stuff. I think it is the best value.
Ultimate has a few more wireless options and some more security stuff.