Wow, this got some attention... Thanks to everyone who replied! Let me try to address some of it...
@Come to the Dark Side "Not sure I follow what you mean by "non-web-access email"
Email that can be accessed not only trough a web interface, but also from a desktop client via POP3/IMAP. Last time I checked, this was a very serious problem with free hosts in the sense of "haha, nope" which is somewhat understandable seeing as how they can't even fling ads at me if I'm not using their web interface. Admittedly, that check was some time ago.
@_LC_ "Is this a joke? Employ your search engine of choice and enter “best free e-mail providers”
Rest assured, certainly not a joke. See reply above. I did, and quite literally the only free ones I found were Google, Yahoo and GMX. Concerning the latter, see also below.
@Jamie Jones "Is your issue with the service, or the apps?"
Strictly speaking: neither, or both - While Gmail is perfectly usable as-is, I'm not appreciating all the snoop going on; but if I leave Google, obviously both the app AND the service would need to go.
@DavCrav "I downloaded WeMail for that. Works like GMail, accesses your GMail inbox [...]"
Thanks for the suggestion, that app might come in handy yet...
@Dan 55 "You need a webmail provider that offers IMAP IDLE and an Android client. If you can't find the info any other way you can test if it's got IMAP IDLE by telnetting to the IMAP server and port. If you want a quick answer try GMX.com with K9 Mail on Android."
Ok, IMAP IDLE might work, further studies needed. As for GMX, they can die in a fire, hopefully. I did have an account with them which they simply booted me out of without explanation citing only unidentified ToS crimes. Which is bullshit, considering that I really, really, REALLY wasn't doing much anything at all with the account and absolutely definitely nothing that would have been against their ToS . Nevertheless, after an appeal the only answer I got was that their decision stands, for mysterious reasons that continue to be none of my business, apparently. So pardon me if I hope to see them firebombed some glorious day, because they definitely deserve it.
@David Nash "Just get a domain and a simple mail service from one of many providers (I use 1&1)"
See above - last checked, there was NO such thing as POP/IMAP accessible free mail outside those Big Three. I am not sure how to find any non-free but reasonable ones that would be worth moving to from Gmail (after all I really don't want all the exact same downsides and some more with none of the upsides) ,but thanks for the tip-off, I'll look into 1&1.
@ Claptrap314 "I find it weird that no one attacked your premises that 1) an email client with your desired features should be available for free and 2) you should be notified about personal emails instantly while at work."
1) You may have overlooked the "or low-cost" part in the original post; at least concerning the service - I do have a free email client on desktop (Thunderbird) thank you very much and my phone does have a built-in generic email client - all I would be interested in is some mechanism that would notify me near-instantly when I get new mail, like Gmail Push does. Which brings us to:
2) You may be forgiven for not realising that very much unlike some people's Facebook stream, my email gets 5-6 mails total on a good day, essentially none of which are personal in nature (but rather formulaic notifications from standard sources such as merchants, Kickstarter, Patreon etc.), which I spend roughly thirty seconds on to parse, each. And my employer can fuck the fucking fuck off and die if he doesn't like that - hell will shatter to a zillion tiny bits due to frost shrinkage stress before you'll manage to guilt trip me for spending that kind of amount of "my employer's time" on that. No offence, natch.
"I'm not ready to cede either of these points."
That's OK. Me neither.