I'd like to put in another vote for Debian or Mint. Fedora is easy to work with as well.
Really though, any distro you choose will have a similar selection of software available. RPM or DEB...it doesn't really matter. Either one is just a way to install the software you want.
Each distro has a different feel, kind of like different cars suit different people. The only way is to test drive a bunch and see what you think. If you're not sure what you like, I definitely recommend using VMWare or VirtualBox to try out different ones before you spend a great deal of time installing and reinstalling and re-reinstalling...
When you find your distro, it will just seem right. There are no best distributions. I went through at least half a dozen before I found MY distro (Debian).
Good luck. Don't give up. It's worth it.