I'd recommend soldier, class has a lot of depth and one of the easier classes to do ok as as a new player.
Maps
Goldrush - Various stages so less monotony, relatively easy to find servers. Great starter payload.
Dustbowl - Various stages, clear defined Capture points. Really easy to find servers.
Once getting past those Maps
2Fort - Has water (and all the various dumb things that go on with that) and the middle area is great for learning rocket jumps, sniper is very linear and the basics can be learned quickly. Extremely easy to find servers for.(I wouldn't spend to much time on this map cause objective based gameplay will be nigh pointless on most servers)
Badwater - Definitely the best static map for learning to play with a team and doing the objective. Not terribly long, all classes are meaningful in a pub environment in various areas of the map. Easy to find servers for, etc.
After that they should be ready for damn near any map.
Not sure how you feel about violence, but you can use silly gibs and pyrovision works on all the above maps.