Tatie says he would personally go with a paladin.
The keyword there is "personally," as it is completely a personal descision, and the class you choose is up to what you WANT to play, not what others tell you to play. No class is better than the other; they are just suited to different playing styles.
The Armsman: No magic, just weapons. May wear platemail at level 15; may use polearms (halberds, spears, etc). Not too fancy... your basic fighter.
The Mercenary: Duel-wielding rogueish fighter. Hits are not as painful, but the mercenary attacks very quickly. He also has many positional combat moves (attacking from the back, the side, etc.) If you want a fast, sneaky fighter, go with the Mercenary.
The Paladin: A "healer/fighter hybrid" according to Mythic, but really, the Paladin is mainly a fighter with some healing abilities. If you'd like to be wanted in a group, this is the class for you. Great for soloing too. May wear platemail at level 20.
The Reaver (SI): A "fighter/necromancer hybrid," though it's basically a fighter that got into S&M too much. They use whips, chains, and flails ("flexible weapons") to beat the living **** out of their enemies, and they can use spells as well to debuff, damage and do other unpleasant things to foes of Albion.
For a beginner, I would recommend an Armsman, since they are easy to play and there's nothing special about them. They just fight, and that's that. If you want some magical abilities, go with the reaver. If you want to be useful in a group and be able to heal yourself, be a paladin. If you want to be a quick and dextrous fighter, be the mercenary. Really, it's all up to what style you prefer. I hope I was of some help.