jmh:
I don't mind a bit of combat so long as it's not the whole point of the game, i.e. to win the war, and then win the next war, .... So, an explorer type game that involved fighting off the occasional pirate ship, might be ok so long as there were other parts to it, e.g. maps, treasure, problem solving
A lot of games could fit into this category! When I think maps, treasure and problem solving I think the Legend of Zelda games as being the absolute best of this combination. But you'd need a Nintendo console for that (or an emulator).
And the games everyone else has recommended so far I would add my +1 vote for, they're all great.
Considering you haven't mentioned a graphics card in your laptop you should probably stay away from 3D games unless it's an old one. I've heard a lot of good things about Stardew Valley