I think your best bet would be to use an external authentication system that enforced whatever rules you want and use DiscourseConnect - Official Single-Sign-On for Discourse (sso) to connect to it.
I guess you could make a plugin that somehow limited what usernames could require certain things only. It’s hard to imagine how it wouldn’t be frustrating, like a “here are our bizarre password rules, good luck following them” system. But maybe if it was just fruits and numbers it’d be OK? Maybe the plugin could use the suggester to suggest names that it liked somehow. Sounds like a couple days work after you’d figured out the code to implement it.
edit: Well, maybe it’s easier than I thought. It looks like the username suggester has stuff built in to make that somewhat easier, though I can’t quite make sense of it in 4 minutes.