I think it depends on the specific functionality you're talking about. There are features that are nice to have as part of a theme, such as color/style options, layout/navigation options, and anything related to the design and specific to that theme. I'd also put some other things under the theme functionality umbrella, such as Analytics integration for example.

But then there are things that make more sense as a plugin. For example, contact forms. There are many great ones available (both free and paid), and users probably prefer to use them with any theme they want. You wouldn't choose to use a theme because it comes with a great contact form feature, would you?

So i think it can go both ways, depending on the theme, the intended audience (mass consumption? or single client project?) and also depending on the feature.