Personally, I reckon a more open setting would be immense. Imagine travelling from Lordran to Boletaria and then to Verdite (If you've ever been lucky enough to play the King's Field series, also by From) across a huge world, possibly riding on a dragon. Or, heck, an Iron Golem. Battling beasties on the road?
Capcom's Dragon's Dogma sort of had that Dark Souls 'physicality' to it that reminded me greatly of From's masterpiece. It wasn't nearly as hard, but there was more of a similarity to Souls than there was to, say, Skyrim, IMO. Anyway, it worked well for Dogma - it was a great game - I truly believe that template could be well-implemented into a Dark Souls sequal.
What else do you think would be a good addition?