I have a couple favorite "odd" discoveries in Minecraft.
The best, by far, was a desert temple that was partially merged with a house in a desert village. Because the temple now had a door, the villagers would go inside. It's the only time I ever found a temple with actual people inside (and a village priest no less). Pretty cool.
My other favorite weird-structure find was when I loaded an old map in a new version of Minecraft (this causes all sorts of really weird glitches as the coordinates of structures stay the same but the world generation algorithm is often times different). In this case the glitch was an entire large village set out on the ocean off the coast like the buildings were on cobblestone stilts. I used a boat to get out there and build cobblestone walkways so the poor villagers could move around again. It ended up being a sweet base because it was easy to light, totally isolated by the water, and 100% hostile mob free.