I decided that the searching aspects of the gameplay are largely ruined by showing a larger area of the map at larger resolutions, so I've ruled that out as a possible way of dealing with multiple resolutions. Instead I've decided to pinch a trick from console games - the game world will internally always be rendered to a "720p" texture, and then that'll be streched over the full screen to upscale or downscale to the native resolution as appropriate.
I say "720p" because (similar to how tvs do things) there isn't a single fixed resolution, instead it'll always be 720 lines vertically, and the number of horizontal pixels will vary depending on the aspect ratio. So someone with a 16:9 screen will have a virtual resolution of 1280x720, whereas those on 4:3 displays will have 960x720. In windowed mode the virtual resolution always matches the physical window size, so you still get nice 1:1 graphics when viewed like this. For fullscreen the streching may mean you'll get some loss of sharpness but doing it manually in-game gives much better quality than letting the user's TFT do the scaling.
The menus are also drawn over the top with a 720p virtual resolution, but without the render-to-texture step (they're just scaled using the projection matrices). The HUD is the exception to the rule in that it's always rendered over the top at the native resolution instead of the virtual resolution. This is possible since the components are all relatively positioned according to the screen edges.
Different aspect ratios are also handled tv-style in that anything less that 16:9 has bits of the edges chopped off. That's not a problem as it'll just make those with 4:3 displays a little more blinkered. And to avoid having to have scalable menus or multiple menu layouts I just need to keep the important stuff inside the center 4:3 area, which is easy enough now I've got red guidelines to mark off the areas for different aspect ratios.
I think it all works out quite nicely - the code stays (largely) simple because it's all dealing with a single virtual resolution, the whole game looks better because it's natively at somethingx720 instead of 800x600, windowed mode still looks nice and crisp with 1:1 sprites and everyone gets the game in the correct aspect ratio - even in fullscreen.