Lapras could have been a legendary in the first and second generations, I think. There was only one available in game, and enough lore surrounding it (saving sailors from shipwrecks, etc.) that it would have held up to the test.
Unown.
No really, Unown. The only thing that bars it from being legendary is its pitiful stats and its inability to learn anything but Hidden Power. Hardly anything is known about them, you unlock them through puzzles, they have reality warper status when used together, and entire ruins are dedicated to them. If they didn't have worthless stats and learned something other than Hidden Power they would qualify as legendaries easily. Heck they're even in the rare catagory of the Fr/Lg Pokedex, which is only reserved for legendary Pokemon like Mewtwo and Deoxys.