Once again... iPod
Private Browsing - No need for it. The touch is already a 'private' browser. Need to cover your tracks? Theres a history clear button in the Bookmarks -> History section and a History Clear, Cookie Clear, and Cache Clear in the Settings -> Safari section. It's just not needed.
Saving a webpage - There's really no saving of anything in Safari, but again, it's meant to be used with wi-fi. It would need to use more resources for a bigger cache and there's not a lot of breathing room in an OSX installation of this size.
A 'save webpage as a screenshot' to the Photo app would be a neat idea though. Would allow for picture grabs, news article reading, showing friend something weird, etc on the go. (If it didn't compress the picture to an unreadable size that is)
Search within a page - A handy feature, it would be nice if it was there... I really don't use it often though, and would be even less likely to use it on the touch. (Opinion, opinion, I know. Is it really that needed though?)
Open in new page - 100% agree. I had hoped that by clicking and holding a link you would be able to get an option to open it to a new tab (That's my preferred way of reading forums/slashdot). Alas, it is not there. I'm in total agreement with you on that one though.
Google maps - meh, works well enough for me. I just put in the start and end position and get directions. The printable version is perfect for keeping on the touch for driving directions.