Should I create Custom Page Types?

You’ve highlighted the issue of creating custom post types in a theme rather than in a plugin. If the user changes to a new theme then you cannot rely on any functionality in the theme you have created.

Themes can add functionality, but in general should be concerned with the presentation of your site

Plugins will add functionality

Hence this is where I suggest you add the register_post_type code. The Registering Custom Post Types documentation recommends this approach as well, so have a good read through that for more detail.