Preview-as-you-type works very nicely indeed here on Stack Overflow. Many wikis don't do that.
Make it really easy to link between pages, eg. that, as you type, the wiki finds likely pages you may be referring to. That way you can make links without having to know the exact title of a target page, and bouncing on the shift key to WriteInCamelCase, or throwing in square brackets. Make it very easy to link to other websites outside the wiki, too (and by "easy" I do not mean like wikisisters, which, if I remember correctly, is like foowiki:ALinkLikeThis).
Similarly, if you can generate links within text automatically, you could, for example, have a mail system that wikifies your email. You create a wiki page, say, for Joel Spolsky, and references to Joel emails in your inbox become links to that page, which you can find by clicking "what links here". (This probably needs something along the lines of Bayesian filtering to prune the stray references to other Joels... your Bayesian Classifier learns that if the context is smart and getting things done, it's Spolsky. If it's flying Viking kittens, it's morely likely Joel Veich).
A variety of RSS feeds for tracking changes would nice, too. (Diffs, full text, changes on pages I've edited, ...)
Wikipedia has grown a fairly colossal categorisation system ("Fictional Cats", anyone?); laying a taxonomy over a wiki's flat namespace could provide another way for users to find their way around. Wikipedia's doing this a little, but in fairly limited ways so far: there are links to the relevant category lists, but you can't, for example, look for a composer called "Smith".
Similarly, wikis give you this big graph of interconnected nodes, of how closely your community sees the relevant concepts as being. Is that interesting? Is that useful? Does anyone who isn't google want to think about this stuff?
PS. If you believe Paul Graham's definition of Web 2.0 as "Democracy, Don't Maltreat Users, and Javascript works now", wikis are two thirds Web 2.0 already.