I agree with @yabapmatt that without an increase in understanding of what witnesses do and how to choose one you support, the outcome may not be what an optimist might expect. Just having promo boxes on steemit to prompt people to go read an intelligently (and fairly) written informational page about witnessing with links for users to learn more and learn about the witnesses themselves - would be a great start.

Unfortunately, we can come up with nice ideas all day long but from what I am seeing Steemit Inc. are not particularly focused on delivering them anyway currently.

My suggestion is to maybe start up a profile/movement along the lines of @promo-steem that promotes witnessing to raise awareness. This would not rely on Steemit Inc. agreeing to anything or having to dedicate any resources. Witnesses could come together to upvote posts that promote witnessing in general and the posts would have to be neutral to ensure no one witness gets an unfair advantage.