Your easiest bet would be to get an Android and install Busybox, but seeing as you're after something that's actually Linux and not some dalvik spaghetti on top of the kernel, you shouldn't go Android.
You should look into the Nokia N900. It runs Maemo, which is a glorious GNU/Linux distro for your phone with a great community. The phone is a bit outdated and uses a resistive touch screen though. If only Nokia hadn't abandoned the N950. :(
Then there's the Nokia N9. It runs MeeGo with Swipe, which is the ruined version of Maemo. The phone itself is nice and shouldn't slow you down, but it's rather expensive.
Another good phone is HTC HD2. It comes with Windows Mobile by default, but it's supported by almost every mobile OS out there: Windows Phone, Android, Ubuntu, MeeGo, etc! It is, like the N9, still up to date(not overpowered, obviously) and shouldn't slow you down.
You should really check out the Jolla project. It's a team of ex-Nokia employees, who left to continue developing MeeGo. Their OS is called Sailfish and it should run on both the N900 and N9 when it comes out, probably HTC HD2 as well. Sailfish is an absolutely lovely system, just like Maemo and MeeGo, only it will have official support. It even uses a package manager: RPM! Jolla will also be making phones, so stay tuned for that.
Another up and coming Linux-based OS is FirefoxOS AKA Boot to Gecko. This the only mobile OS that's not a "walled garden" and is based on HTML5. This is, out of all mobile OS projects, my favourite.
Then there's Tizen. It was supposed to be a great mobile Linux OS, but the development is so slow that nobody's sure that it'll even come out.
Please look up additional information if you're interested in any of these. I obviously didn't mention everything.