What would stop them from creating an Android app to notify users if an AirTag seems to be travelling with them?

They easily could, agreed.

They even might? It's not unheard of for Apple to release software on other platforms, however uncommon it might be. It's certainly not the kind of thing they do right at the time of release.

I don't imagine you'd get much penetration relative to running it on every device at the OS level, though. Probably rough on the battery running in userspace?

It doesn't seem like it solves a problem most people are likely to have.

They didn't try at all. I wouldn't personally sell a device such as this as I believe it is very ethically grey unless you seriously consider mitigation measures that are available to everyone.