I don't want to sound too biased, BUT (of course there's a but) I think you should give Slackware a shot. I've been using Linux for about 5-6 years and have tried most of the major distributions. I WISH I would've tried Slack sooner. It's not as newbie friendly as MDK tries to be, but the plus side to that is you learn a lot (about LINUX, not MDK). So don't expect any pretty GUI config tools (or advertisements on your desktop and browser menus) but do expect to read, learn, and have a rock solid system! A good place to start is probably http://www.slackware.com/book
Good luck and I hope that you decide to give it a try.