later than 2005 for most people, the first iPhone was released in 2007, first Android phone in 2008, those things made a lot more people practically able to access the Internet from outside, and even then it took until 2009 to 2011 for many people to get one
Google maps didn’t exist prior to the iPhone/android period as well, so people with blackberrys didn’t have access to that before Android/iphone 07-08
I had Google maps on my Nokia SymbianOS phone before the iPhone was released. It worked just as well as modern version but was I little clunkier to use without a touchscreen. I’m pretty sure that Palm Treos had it as well. There where also some other options, I kinda remember Garmin selling map packs for Palm devices. Smartphones existed before android and iPhone, even if they weren’t as widespread they were catching on with the broader consumer before the iPhone was released. You saw more more people getting blackberries for personal use instead of just business.
Are you sure it wasnt another app? What I see is that it launched with the first iPhone. (Was a website previous to print directions like MapQuest and what not)
Google Maps seems to have been launched in 2005, so it did exist, though maybe not as a smartphone app.