GTA has always had a pretty strong focus on narrative as well. The only reason I've never really associated Mafia with the open world genre is it didn't really promote the emergent non sense that you'd see in GTA. It's been quite awhile since I last played it but I don't recall there being much to do outside of the missions. The city felt alive and was fun to take in, but the police chases and blowing random shit up never really lead anywhere except to you dying pretty quickly.
Mafia's missions are still vastly superior to most other similar games, so it's definitely not a mark against it in my books. Raiding that dudes mansion with a shotgun in the middle of the night is still very strong in my mind ![]()