If you plan to release them independently, then release them independently and try to get them both hosted in the WP repository. This will allow you to update the systems remotely and keep people using the most up-to-date system possible.
Then, in your theme, use is_plugin_active() to filter your commands. If you have a theme feature that requires a plugin, use is_plugin_active() to dynamically switch between using the feature or nagging the user to install the plugin.
The important thing to keep in mind is that your theme should still work if the plugins aren’t installed. It doesn’t have to have the same rich feature set, but it also shouldn’t break if they decide to remove or deactivate one of the other plugins.
Alternatively, if you know that a certain plugin isn’t going to change for a very long time (I use a few plugins that only add/remove specific WP filters) you can drop the PHP file into a /library directory with your theme and include() the file in functions.php. Then the functionality is enabled by default – tradeoff is that you’re now maintaining two versions of the plugin (as you mentioned in your original question).