Fedora is my pick for beginners:

1. It has lots of packages available, like ubuntu you can find .rpm available online pretty easy
2. It has a good out of the box experience, not overly customised so you get to do that yourself (if you want, its not necessary)
3. Its got a graphical installer, however its not the best installer. Still way better installation experience than arch or gentoo though for example
4. Its got up to date software