Another improvement would be the introduction of the Bernstein signature scheme with a similar security parameter to the existing ECDSA but a much faster verification. Transactions using the cheaper signatures could get a discount on the fees or be allowed more sigOps. To be clear, the scheme I'm thinking of is
"A secure public-key signature system with extremely fast verification" from about 2000.
ByteCoin
If you wanted to introduce a signature scheme which was much faster but which required more storage, then offset that storage with improved pruning, why not hash based signatures (lamport or similar tree analogs)?
They are quite fast, have fewer security assumptions than other signature schemes (other signatures also become insecure if H() has the same weaknesses which would break lamport), an intuitive security proof, and are strong against proposed QC models (regardless of the real merits of QC attacks, marketing garbage is making the public think that QC's are already a real thing and the true but misleading assertion that bitcoin would fall to some highly hypothetical very large QC is harmful to public confidence, though I don't have a real feel for how harmful it is generally but "OMG QC's break bitcoin" shows up in IRC ever other week or so).
Lamport signatures also allow distributed storage of signature data. You can forget parts of signatures over time at random but still use them for lower confidence validation of the signature, you can also partially validate them for a big speedup.
