I have both Icon and the SE. If a camera isn't all that important I would recommend the SE.
Currently using my SE with the preview 8.1. Yes, you can get Here Maps and download the maps for offline use. Most all of the Nokia apps are camera related. I really don't miss any of them. Samsung has some of their own apps as well. Their App Folder is actually better than Nokia's.
The Icon is a good phone, the main drawbacks to me were limited storage, not very comfortable to hold, and it's very heavy.
The SE is very light. Fits in the hand very nicely, and it can take a 128 SD card. Another $10 and you can get wireless charging too. As far as support goes, the only Samsungs I'm aware of having that problem are the WP 7's and that's a dead end anyway. Haven't heard of that problem with the ATIV series. Might be some carriers out there not updating theirs but Verizon has been on the ball. The SE will be supported.
If I were you I wouldn't be shopping phones right now, just price brackets. More phones will be released between now and fall which may catch your eye.