I've used both SuSE and Redhat. Both are very easy to
install. With SuSE you get more bang for your buck,
with their great manuals and tons of cd's full of
programs. But you can't download SuSE. Redhat on the
other hand is free to download the base version.

Thats just my suggestions on what I know.

While I dont use it now but Mandrake has always been good for a new
user.