A good rule-of-thumb is that anything a user would expect to keep after changing themes belongs in a plugin. This includes custom post types, taxonomies, metaboxes, shortcodes, and customizations to other plugins (like my Display Posts Shortcode snippets).
For specific functionality that’s reusable and/or the client might want to selectively disable, it’s best to build as its own plugin. Many times I’ll turn these into public plugins.
For everything else that’s project-specific but should be theme-independent, I put in a plugin called Core Functionality. Of course you’ll want to delete everything that’s not relevant – I have the code for post types, taxonomies, and metaboxes in there because they are used most often.