Themes

I would strongly recommend updating initially - themes have changed since 2.7 with many improvements and changes, including Bootstrap 4 to support even better responsiveness (Moodle latest stable is now 3.7)

As a personal recommendation, I would then stick to considering the themes in the plugins database, unless you are able to contact the developer in person to ensure you have ongoing support (probably then paid for). Plugins database themes are more likely to be able to be supported through the community, although several of them (Adaptable, Fordson and all of Gareth's themes) are brilliantly supported by the authors/developers both through the excellent Themes community and directly.
From there on it becomes a case of what do you want from a theme - basic allowing you to customise it yourself (even Boost is highly customisable with a modicum of css knowledge), lots of settings to customise it, and/or lots of additional features. Don't base your decision on specific colours/background images etc - they are very easy to change! - but more on the layout, available settings and features in the theme.

I'd also recommend setting up a test system and trying a few of them out to see what you like about them

If you are upgrading, something to keep in mind: Any theme not based on Boost(Bootstrap 4) will be obsolete after Moodle 3.7.
Long story short, many of the most popular themes were based on an older version of Bootstrap and that version got dropped in Moodle 3.7.

Some themes have ended development or the developers are re-inventing new themes to cope with the change. It was quite drastic change and sometimes easier to start over than try and fix all the things that changed.

So, if you pick a theme today and only upgrade to a version below Moodle 3.7 you might run into an issue where you cannot upgrade any further without switching your theme again because it might not be compatible. Fordson, Moove, Foundation, and Adaptable (Adaptable is working on upgrading) are great choices out of the Moodle.org repository.

The best paid theme is REMUI. Most of the themes I have seen on themeforest are eye-candy and do not have people involved in teaching and learning building them. There is a difference because themes built around teacher and user feedback are going to be geared towards enhancing learning and not flashy eye-candy. The difference is under the hood where beyond just style and layout you will find features and things that actually enhance Moodle for teachers and students.