Have a chat with the new players about their fantasy tastes and preferrences. Who is their favorite fantasy/mythological character? Players who identify easily with, say Obi Wan Knaobi, Luke Skywalker or King Arthur will probably feel comfortable playing a Paladin; players who like Bilbo Baggins or Garret (from Thief: The Dark Project) will probably like playing a Rogue; if they like Hercules, Boromir or Conan will get along with fighters quite easily (hell, almost everyone will get into a fighter easily); and so on. In short, talk with them about their fantasy preferrences and then slowly move the conversation towards which archetypes they'll want to play.
I'd recommend you to stick to the PHB for the time being - too many options might confuse new players, and the PHB includes most of the basic fantasy archetypes and enough feats/skills/spells/gear nescery to start playing.
Class-wise, I'd recommend the following:
1) Fighter - the most basic archetype and the easiest class to play; the only marginally complex part of it is feat selection, and then it only happens when the character levels, and not during the adventure itself. Better yet, this class isn't going to die easily, and is going to have a very active role in combat.
2) Barbarian - another fantasy staple; and even less complex than the Fighter. Also, when combat is about, this character grabs the spotlight - and kicks ass.
3) Paladin - the Knight in Shining Armor (or even Superhero) archetype; players who are into heroics will easily fit into this role. Also, has some interesting abilities but nothing too complex; also a very straightforward combat class.
4) Rogue - another fantasy archetype, plus most of his abilities are skills, which are quite simple to use (basic D20 mechanic), are unlimited-use and usually don't require the player to remember durations, ranges, areas of effect and so on. The main complexity here is in terms of skills, but if you'll help the players during CharGen it won't be THAT complex. Somewhat less sturdy in combat, and needs a little more tactical thinking, but can still hold his own.
5) Sorcerer - for players interested in magic. The only complexity issue here is spell selection, but if you help them at chargen, this won't be much of a problem, and this class doesn't require you to choose every game-day spells from a list to memorize. Just give them the staples and let them choose what to use in play. The other issue here would be combat survivability - remind players of Sorcerers that they aren't good warriors, and encourage them to use their spells from a distance; then they'll shine (just wait till they reach level 6 and get a Fireball...).