That's much, much less true than it used to be. These days there's great tools for managing and modifying selinux policy, and much better reporting of what was denied, when and why, and how to fix it.
The "Selinux is too hard for mortals" thing is a relic from the early days of its inclusion into linux, and turning around this attitude is important.
Can you be more specific? There's lots of different tools available - there might be some better options available than what you're using.
And while tools that change things (e.g. setting booleans, changing context rules, etc) are unlikely to be instant in the near future, as the policy needs to be re-compiled, this has been improved, particularly for booleans.
You can also batch updates together, which is a much nicer experience if you're trying to set a bunch of things at once. e.g. semanage -i <( echo -e "boolean -m --on httpd_use_nfs\n boolean -m --on httpd_use_sasl")
That said, "this admin command I rarely use takes 30s to run" (30s seems to be about the average on RHEL 6/7) is to me an odd reason to try to avoid an important security feature.
I don't recall the last time I had to do a full relabel on a production system. Not saying it hasn't happened, but I can't recall an instance.
Overall, I spend less time managing SELinux (and that includes the custom policies I maintain) than I do managing IPTables. It's really not the nightmare it's made out to be.
Depends how well integrated it is into the system. I tried to add any MAC to my Arch and discovered that: 1. doing everything from scratch for Tomoyo, including plugging it into grub config and creating your own policies is easier than even getting proper tools for selinux 2. Tomoyo behaves like Apparmor (policies on names not inodes), but can do more (ioctls, devices, more granular network controls) 3. Nobody uses Tomoyo and I really don't get why...
Yeah, it's going to be an uphill struggle on any distro that it isn't already well integrated into - there's a lot of effort that goes into making SELinux in fedora/RHEL/etc JustWork(tm). Duplicating this on a distro without tight SELinux integration is going to be hard - but I tend to feel that if you use arch, linux from scratch or other similar distro, it's not really fair to blame SELinux ;)
It's not that it's too hard for mortals, but that it provides a level of resistance people are not used to, and don't know how to deal with, and where the easiest solution is to turn it off.
Whereas on Android, people expect the barrier, and developers don't expect to be able to disable it.
The "Selinux is too hard for mortals" thing is a relic from the early days of its inclusion into linux, and turning around this attitude is important.