Are rainbow tables still useful? With unsalted passwords becoming rare, and stream ciphers having a significantly large state, are there currently any widely deployed systems still vulnerable to such time-memory-data trade-off attacks?

If I were to show a small generic improvement to rainbow tables, what would be a good problem to demonstrate on?
If you just want to provide a generic improvement I'd just target password hashing. If you think that directly running passwords through a cryptographic hash is history then I can show you plenty of StackOverflow questions where it is still being performed.

For a generic attack you don't need a new problem; just focus on your improvement and let your solution be interesting on its own merit.