This post started first as a side note to a post about Free Software Trajan Pro alternatives.
I've found at least two free fonts possibly similar to the non-free Segoe UI: Iwona, Quercus.
Another alternative to Segoe UI is the Ubuntu font family, which consists of
• Ubuntu Condensed, and
• Ubuntu Monospace.
Note that fonts of the Ubuntu Font Family are governed under the Ubuntu Font License, which is not compatible with Debian Free Software Guidelines (DFSG) and not approved by OSI. Nevertheless, the Ubuntu Font License is copyleft and fairly permissive.
Nevertheless, Ubuntu Font Family fonts have been included into use with Google Docs, so it seems that they have already earned themselves quite a reputation.