Hunter - started as this class myself. The axe is kinda neat if a bit slow, but in the beginning of the game, arrows are SO expensive even if they're really useful in some situations. By the time arrows become generally economically viable for regular fights, you'll probably have found/bought a bow for your character anyway.
Wanderer - can't say much about this. Kinda similar to a Hunter but without a bow and more agile. More dependant on getting in, dealing a few quick blows and getting out.
Magician - decent starting class because magic is so powerful in Demon's Souls, however, Royalty is a better starting choice. The spells don't pack quite as much punch, but you can cast them a whole lot more.
Knight - tankiest of classes, wearing the full armor set will hinder your speed and dodging, but you can always take a piece or 2 off and still have good defense, since the set is really good. Can branch off into spells and miracles easily.
I guess I would recommend either Knight or Royalty (or Magician). Playing either Wanderer or Hunter will require you to do quite a bit of melee with gear that's not exceptionally good if you're completely new to the series.
The Red Eye Knights are definitely an end-game enemy