A new line of Linux-based phones is scheduled to be available soon. The Neo1973 is the first phone from this family of phones. The GSM phone has a 640x480 touchscreen, and an A-GPS receiver. In addition to the standard applications, you can install new applications using an "application manager" interface.
They are expecting a follow-up model that includes both WiFi and Bluetooth.
I think that something like this has the potential to be a challenger to Apple's iPhone.