I'd been holding off getting one because I didn't want a brick in my pocket, then I saw the Samsung Galaxy Y, which I've had for a month or so. That's not long to give a decent report on how robust it is (and TBH the build quality isn't great) but I've been reasonably impressed with it. Large enough to be useful but not much bigger than my old "non-smart" phone. It's a full on Android 2.3 phone with WiFi, GPS, 3-axis accelerometer, 3 axis magnetometer, querty keyboard, apps, etc. The GPS seems pretty good and sensitive enough to work indoors. I live in a poor reception area and get better reception than my old phone.
All in all it may not be the most solidly built but seems like value for money at under ?100 for a full-on smart phone.