I highly recommend City. It takes everything from the first game and improves it; that includes gadgets, roaming and combat. Oh man, the combat needed improvement. And true to the name of the game, the city is quite large, containing a bunch of clever Riddler puzzles and side missions.
And once you get the grapple upgrade, roaming the city feels (even more) seamless and free.
It's definitely much less restrictive than the first game, for obvious reasons.