I will give my suggestion to Kingdoms of Amalur and Dragon's Dogma. Just keep in mind, both were released originally on last gen consoles, and that Neither of them have a very good story (In DD's case, It might have had a good story hidden somewhere, but it was delivered horribly). What these games do have, however, is great combat and classes. You can switch classes at any time, and all of them feel useful and fun. DD has more of a traditional class system, with 9 classes to chose from (3 basic warrior/mage/rogue, 3 advanced classes, and 3 hybrid classes), whereas KoA lets you put points into abilities, weapons, and stats from the 3 basic warrior/mage/rogue archetypes, letting you specialize or make a hybrid. Both games are open world, but each of them have different flaws. KoA has the MMO zones syndrome, where an area is just a semi-large landmass being connected to the others by a small pathway and a loading screen. DD on the other hand, has a well-crafted open world, but is plagued by non-random enemy spawns, a limited fast-travel system (you have to use items to fast-travel), and only one (and a half) town. That said though, if you can look past some of their flaws, the combat is more than enough to carry these games to the end.
I personally couldn't get into dark souls, on account of its terrible level design (also the game's reputation works against itself sometimes), but I seem to be in the minority there.