The Tenchu series sprung to mind for me. The original game placed great emphasis on stealth, and was actually released before MGS came along and made stealth gameplay popular. In terms of more high-profile titles, the Hitman series probably counts, and although I haven't played Assassin's Creed I think I'm right in saying that avoiding detection is a priority there.