For option 1; Second hand market, great condition phones - you could get.
- iPhone 3G/s have been going for 2k/2.5k (though I don't consider it a smartphone) or
- Nokia N97 (or similar) or
- Blackberry Bold 9000 (which is the standout amongst the three IMO)
No touch screen on the BlackBerry Bold, but great resolution on that small screen and you may also consider a first or perhaps second gen BB Storm if you want touchscreen.
As for new phones - I can't think of any besides a BB Curve 8520 that you can get for R2k.