if you build your lego structure upside down in a tank of clean water, when you are done with it, most of the lego will be filled with water instead of air, and they may not float, or at least will be way less boyant. I think if lego is used tastefully, it could be very fun...
one idea is to use the yellow or green 1x2 and 1x4 bricks to make a wall, inserting the 1x2's that have an axel hole in the center, every so often... and then planting moss in the holes to become a moss wall. it could have an irregular edge, looking like a crumbling wall, and you could probably seed some green hairy algae or something across the top to make it look more natural.
I say GO Lego!