Well, if you go back to 2003, there was the Motorola A760, which looked a lot like current android phone but without capacitive touch (resistive touch/stylus, no keyboard though). Oh, and it ran linux, and apps via java.
Yeah, I had a P800 running UIQ back in the day. But I think the bottom line is that if you put a UIQ phone, a WinCE phone, an iPhone, and a G1 in a lineup, the G1 would be a lot closer to the iPhone than the others. And the similarity has only increased over time.
Know what would be a heck of a lot closer? A Clie TH55.