Gmail push support out of the box on the iphone 4 launch OS doesn’t seem to work as advertised.
Use google sync instead, which makes you speak directly to googles servers. Setup instructions here.
I tested it, I get my email notifications within 1 or 2 seconds.
http://www.google.com/support/mobile/bin/answer.py?answer=138740&topic=14252
Yuji Tomita 