Call of Duty is definitely not one, it is very easy to pick up and play and after you play each map about 5 times you'll learn the regular hot spots and be able to survive mostly. A lot has to do with luck though.
If shooters are you're thing, I would suggest TF2 (good game and its free). Alternatively try to stick to shooters that don't have such small health bars that you die in 1-2 hits. Older Halos, KZ2, Resistance 2.
RTS games are also good. Usually getting through the first couple levels in the campaign will teach you enough to play the game, but they are notoriously hard to master.
Also I would highly recommend you try out League of Legends. Great game, good fun, but since its almost entirely PvP it is very difficult to master since it requires a good ability to adapt.
You said not fighting games which is a shame cause those are the purest example, but basically you want to stick to games that have a large focus on PvP, and do not contain one or too many stupid exploitable tactics (see camping and noob tubing).