Where, When, & How to Properly Flush Rewrite Rules Within the Scope of a Plugin?

The best place to flush rewrite rules is on plugin activation/deactivation.

function myplugin_activate() {
    // register taxonomies/post types here
    flush_rewrite_rules();
}

register_activation_hook( __FILE__, 'myplugin_activate' );

function myplugin_deactivate() {
    flush_rewrite_rules();
}
register_deactivation_hook( __FILE__, 'myplugin_deactivate' );

See the codex article

Apologies in advance, I didn’t make it all the way through your question, so this is a bit of a cookie cutter response.