An increased character cap would be very nice. I’ve kept several slots empty for a while now on my main account, just in case a new allied race or class was coming along, and have put several alts on my currently inactive alt account.
On deleted characters: I don’t really delete a lot of my characters, but I did recently restore one that I deleted way back in Cataclysm. It was like traveling through time, a very cool experience, so at least it does seem like characters stay in the system for a really long time.