That sounds off. I had Google Maps on my Samsung flip-phone somewhere around 2007 - can't remember if it was before or after the iPhone's release though.
Those are just other clients to the Google Maps service, and some of those clients might have predated the iPhone. It just happens that the client on early iPhones was written by Apple, but clients on other platforms may have been developed by Google.
The impressive thing about the client on iPhone wasn't the maps themselves as such, other phones had maps, it was the ease and fluidity of navigation using multi-touch gestures, and the simple integration with system services such as location services. Bear in mind phones back then didn't have pre-emptive multitasking.
Nokia n770 "an internet tablet", had maemo mapper which used the Google Map data. It worked well, the main problem is that n770 had no WAN chip. You could preload map tiles though.
This was before the iphone, and years before google maps would work offline.
