Wow... I just started a game as Spain, and it's uncanny how similar it has been to yours so far. At first I figured I'd just want to go for the first three religions, and it seems to only viable way to do that is as Spain. It may be possible with other civs, but not very likely on Prince.
Just like you, I started on a lake, though I wasn't lucky enough to start out by the ocean too. I got the first three religions with little problem, although I wasn't lucky enough to pop masonry from a hut like you, so it took a little while longer. While all of this research was going on, I sent my lone warrior out scouting to discover Elizabeth and Peter on my island. It would have been difficult to hem them both in, so I figured to go for Lizzie, the easier target, first since it would only take two to block her off. I spent most of my time building stonehenge, although I figured I had a good enough lead on it, so I started a settler halfway through, and sent it out with my lone warrior (with forest 2 and combat 1 from popping two experience huts!)
After finishing stonehenge, I built a worker, and then an archer, and finally another settler to block off the English (though she did manage to place her city almost exactly where I was going to, so it made my job a bit more difficult.) Then I built another archer to stay in Madrid and started on the Oracle to get myself a nice tech lead. During all of this construction, I had researched Hunting, Animal Husbandry and finally Priesthood, and built another settler archer from my second city to take a marble spot which was connected about halfway through the construction of the oracle to make my job a bit easier.
Once the Oracle was built, I was only a few turns away from my great prophet, and Theocracy and Code of Laws were about the two most expensive techs available to me, so I figured I might as well take them and get Christianity and Confucianism too. I then beelined for Alphabet to be able to trade techs with Petey and Lizzie.
A bit later on, I remembered how you guys got Islam from your second Prophet and figured what the hell, I might as well go for it and started researching Divine Rght about 3 turns before my second prophet came. The turn after I started researching Divine Right, lo and behold, Taoism is founded in Hastings right after Elizabeth gets a couple of Great People... I couldn't believe it. I thought I might have a chance at getting it after Islam, but I guess not. At some point in there, I had also built the great library and the Sistine Chapel... And right now I'm working on the Chichen Itza! If only I could get that one stone on the island hooked up, the Sprial Minaret would be mine.
Here are some screenshots:
I have a feeling that the Stonehenge/Oracle combo is a bit overpowering early game... I don't know if it's possible to get both on harder levels than Prince, but the combo gives easy access to at least three pretty advanced techs for that era, with the potential for three religions to boot. While it's entirely possible for one to miss all three of the early religions in a Monarch or higher game, if they concentrate purely on getting these two wonders, they could get quite a good tech lead on the AI along with three holy cities.