Based on how I think you are defining complex and verbose I would say it is mostly verbose with a tiny bit of complexity brought in by the policy build structure. Most of the "complexity" that people associate with SELinux policy is the number of rules that the policy is expanded out to. While there might be some optimizations that can be done on the policy to remove duplicate rules or rules that may grant the same information flow it balances being lean with the ability to debug the policy.
The reality of the situation is this. SELinux is a default deny system where the policy consists of rules that say what is allowed. When you do this you have to basically model in policy the entire system and all applications running on it. To make it easier for people to write policy the reference policy has been broken up into several layers and exposes interfaces for policy writers to use instead of writing raw allow rules. However this yields a large policy because the system we're trying to protect is large and complex. We have examples of much smaller policies being written and applied but these are on more special purpose deployments where the set of deployed applications is much smaller.
Now KaiGai is right in that a distro's integration of SELinux is very important. Since you're describing in policy the default behavior of the system it is important that all of the distro specific nuances are addressed. You can see this in the reference policy in places where there are distro checks for debian vs fedora. This is where most of the issues that people have with SELinux stem from. Dan Walsh has an article on his blog titled "4 things SELinux is trying to tell you" (or something like that) that explains SELinux problems.
That said Fedora/RHEL and Debian/Ubuntu have well supported SELinux integration with SUSE to make progress. Its worth noting that I couldn't find a blog posting from Tom on SELinux support in opensuse 11.3 so its possible it has gotten better since his description of what he wants in 11.2. If you use the system as it is deployed out of the box then the SELinux policy should match up with the running system. If there are denials then that is a policy bug and should be reported to the guys at Tresys or through your distro specific bug tracking site. The problems are when people start moving things to non-standard places and then don't realize that just like the ugo bits they may have to set the SELinux label on the file as well. Dan's presentation and paper give a really good explination of this so I'd recommend reating that rather than having me repeat it here.