Escape to New York

This game is set on the Titanic, and borrows a small bit from that show. There's no romance, but you play a thieving character who must hide from the law on the ship, including using an axe on metal and having a special painting.

The game is huge, but it comes with a very helpful map.

The main puzzles are fairly well clued, but there are a host of other puzzles. The fussy mechanic of opening and closing the suitcase, as well as the maze-like map, is fairly frustrating, though.