You mentioned the G1, and really if you can find one in your price go for it. I understand you not liking the extra charge, but it's sooooo worth it.
I've had my G1 for 5-6 months now, and I can't say enough good things about it. It absolutely rocks. And with the new cupcake update coming out by the end of this month, it's gonna get even better.
I've played with the Behold, and I didn't really like it that much. The G1 seemed quicker while going between apps, and I really didn't like the on screen keyboard on it. I've never gotten a chance to play with the Memoir.
So why does the G1's data plan cost more then the data plan for the other phones? It wasn't like that here.