I think turning off the "Stealth mode" in your Firewall may fix the problem.
Resetting the PRAM doesn't really work.
What I think the problem could very well be caused by "Stealth mode" being turned on, causing the wi-fi ISP fail to detect a response from your computer (as if your wi-fi connection never existed under stealth mode).
That caused Lion/Safari to keep waiting for the wi-fi connection handshake to be established, but never got a response from the ISP (because the ISP would not know you existed in stealth).
This causes the classic "deadlock" when your Mac waits for the wi-fi ISP to respond, and the wi-fi ISP never knew you existed, so both sit there and wait forever.
Because Lion's Airport's auto-join algorithm failed to detect the wi-fi probe from the ISP, it never popup the auto-join dialog window to ask you to authenticate as a user to release the IP address to connect with the internet. (That is why it works for other wi-fi connections that does not ask for authentication, and it works for the WEP and WPA authentication even with stealth mode on.)
I think that is why not only Safari, but also any Apple-made apps that uses the internet to connect, including iCloud and Mail, will also hang just like Safari.
The reason why Firefox works, I think is because Firefox (a pre-Lion app) does not wait for Airport to trigger the Auto-join dialog-window , and went ahead to probe the wi-fi ISP connection explicitly, thus bypassing the stealth mode, and get a response from the ISP.
But since all Apple-made apps are Lion-compatible, and rely on Auto-join to establish the wi-fi connection, if you are in stealth mode, auto-join fails.
In fact, if you put your computer to sleep or inactive for awhile, the wi-fi ISP will time-out, which cut off your IP connection. When you wake up, Lion still assumes you were connected to the deactivated IP, without asking for a new connection, that is when it hangs again too – not just during your initial connection, but also any subsequent timed-out connections.