Share difficulty isn't really a round time. It's more of a threshold. You're calculating shares all the time, but most of them have a value below the difficulty threshold, so you're not submitting them.
A share difficulty of 500k doesn't mean you're mining away on a huge chunk for ages (which would be bad for fast block times), it just means that you only submit a share when it randomly happens to have a value over 500k. But that single share wouldn't be any more likely to be rejected than any diff 16 share.
Also, empirically speaking, Middlecoin has a difficulty of 1024 but I never had particularly high reject rates there, always around 2-3%.
Wouldn't a 16 share take less time to compute compare to a 1024 share?
Middlecoin also have multiple servers, which I think is one of the biggest problem with CM right now.
No, it wouldn't. Watch your cgminer (or whatever you use) closely. You sometimes get huge shares, in the hundreds of thousands or even millions, out of nowhere. These don't take long to compute, they're just unlikely to happen.
And yeah... more servers would be neat indeed.