UPNP seems to work well for the reference client. What's the situation
there on Android?
Not sure - it could be investigated. I think UPNP is an entirely userspace-implementable protocol, so in theory it could be done by a userspace library (even libminiupnp - java is not a requirement on android)
I leave my phone plugged in and connected via wifi for most of the day;
lots of people do that.
I suspect you mean "I think lots of people do that". I'm not so sure. We could potentially run an experiment in the Android app to measure how many users are in a position to contribute back, but just because you have wifi doesn't mean you can reconfigure it using UPnP. That helps a lot in home networks, but at the office it doesn't help.
I'm wary of a ton of work being put in to achieve not very much here. Satoshi's original vision was always that millions of users were supported by 100,000 or so nodes. I don't think that's unreasonable over the long term.
Besides, prioritisation isn't very hard. Nodes can just hand clients a signed timestamp which they remember. When re-connecting, the signed timestamp is handed back to the node and it gives priority to those with old timestamps. No state is required on the node side. Signing and checking can be passed onto the general ECDSA thread pool that works its way through pending signature operations, they'd be prioritised lower than checking blocks/broadcasts.