The Command and Conquer series are more for the intermediate RTS gamer, but I do suggest buying Warcraft 3 and playing DOTA. If you must play WWII RTSes, Company of Heroes is an excellent choice. I'm currently playing Supreme Commander, but it's a little to overwhelming for the newbie.

I'd recommend some of the free TBS games around. There's at least 1848, Advanced Strategic Command, Battle for Wesnoth, Civ-evolution, FreeCiv, FreeCol, Leylines, Steel Panthers : World at War, Steel Panthers: World War II, Steel Panthers: Main Battle Tank, The War Engine, Titans of Steel: Warring Suns, TribleA and UFO : Alien Invasion.
There's also Gary Grigsby's Pacific War: Matrix Edition and Gary Grigsby's War in Russia: Matrix Edition but they are definately not for new players (heck Pacific War is too much to handle for many experienced players as well).
Desciptions and links to all the games and more can be found from my site's links section.

The Panzer General series is good. Turn-based, not a lot of resources beyond your troops and some prestige points to spend occassionally.
Heroes of Might and Magic 2 is excellent as well. Eplore the map, build your cities, build troops, lead them into battle--all turn-based. I like the graphics as well: very pretty, colorful 2D sprites. As I've said here before, it's like playing an animated, stained-glass window.
I love the Civilization games, but that may be more complex than what you are wanting right now.

Off topic alert!
Every time this thread comes up all I can think of is the Saw films...
"I want to play a game"

i recommend company of heroes is kinda sink or swim for world war 2 a fun but more complex game would be creative assembly's total war series Rome total war in particular

A few suggestions (some new, some already mentioned):
- For WWII theme, how about Axis and Allies. Plays like the board version (pretty basic) and customizable.
- Of course the GOG staples--Fallout 1&2, JA2, etc.
- Fantasy theme--Age of Wonders, Warlords IV
- Space/sci-fi theme--Galciv2 from Stardock, Space Rangers 2, X-Com (1 or 2), Master of Orion 2
-Space RTS--Sins of a Solar Empire (Stardock). I SUCK at RTS games, but his one is paced more like a TBS and is an excellent game.
Hope this helps.

The "Total War" series of games might provide the right balance of tactics, strategy, and simplicity. Check it out - there should be demos around for the more recent games.
In fact, try and find demos for every game that's mentioned in this thread. They're fairly easy to find and you'll know straight away which ones are too complicated.
Also, I would recommend Civilization (probably Civ 4, on account of it being the most recent and popular).
In addition to decent strategy, depth and AI, it has quite simple controls and several mods available - including World War scenarios and mods that you could jump right into.

Shameless advertising
DO try it

Do you have a GBA or a DS?
If so pick up an Advance Wars game... or any Fire Emblem game. Best turn based games ever....

Pity the story and dialouge was written by a 12 year old. I did like it though, and enjoyed the soundtrack to which alot of people seemed to hate.

Its anime based... the story and dialogue is almost always written by a 12 year old (Totoro excluded of course...) ;-)
But i liked it, it had a lot of charm. I'd take it's story over a lot of the grim, overblown sci-fi rip-off stories in other strategy games.
I'm having more fun playing Fire Emblem on my DS right now than I've had with any other game (on any platform) for the last 12 months. Its like they took the story from a final fantasy game, without making me sit through all the horrendous gameplay...