Any of the awesome Android phones from the last generation?
I'm using a (now) 18 month old Xperia Arc which I love. It still uses Android 2.3, and only a single core processor, but it does everything I want, and it does them all pretty darned well (admittedly, I use it more as a camera than a computer). There were a bunch of similar phones all released at the same time: Original Galaxy, LG Optimus 2, etc. I see lots of them show up on kijiji used for under $200.
You give up some up-to-the-minute features, and save a whack of cash. Personally I'd look for one cheap, in good condition, unlock it and put Cyanogen mod on it, then use whatever carrier you wanted.
Edit to clarify: I've had my Xperia since new, but I would happily buy any of the top-shelf phones from that era if they were in really good condition. When I replace my phone several years from now, I will look to replace it with a one or two year old used example in pristine condition.