How bad is flush_rules() on init hook?

It sounds like you misunderstand how to add rewrite rules as your structure is relatively common and should not require flushing the rules on every page load.

The impact depends on your set of rewrite rules, and the codex is somewhat outdated and I don’t think it is as bad as it used to be several versions ago, but still it is updating an option with a possibility that it will be written to the DB. Your site might actually survive a write to the DB on every page load (some stats plugins used to do it) but it is totally not scalable and your site will crush once it get traffic.