Exactly. I was using online app Stores in 2006 and 2007 to buy, download and install apps on my Windows Mobile phones.
Password managers, device themes, various other apps - you name it, they were all available.
People act like the App Store was some miraculous new thing apple invented, but these existed long before iPhone.
Windows Mobile also had other nice things that iPhone took years to get like copy/paste, GPS navigation, voice control, SD card support (iPhone still doesn’t have it), theming etc
The only thing apple did was use a glass screen instead of plastic and made a finger friendly and good looking UI. That’s it.
Yes these made the phone more appealing to the average user who only knew flip phones but for us nerds using Windows Mobile, it wasn’t a massive step forward.
HTC had already been making finger friendly themes but they could be a little sluggish because the CPU market hadn’t really taken off yet.
There was a Russian company that I bought many themes from for my HTC. They were really nice. I just can’t remember the name anymore.