Agreed on the replacement fonts. The only issues I've ever had were to do
with documents that used tables for layout, and used Calibri as a font. When
I opened it with LibreOffice the table looked very messed up, but I soon
realised that changing the font size would fix it.
In general it's bad to have layouts that rely on a font size anyway. But
besides one or two minor issues I've had no problems with LibreOffice! :)
Some of my favourite free fonts:
FreeSans and Liberation Sans: can replace Arial and Helvetica
DejaVu Sans: can replace Verdana
FreeSerif and Liberation Serif: can replace Times
Droid Sans: can replace Segoe and Calibri
DejaVu Serif: can replace Georgia and Cambria
Century Schoolbook L and URW Bookman L are also nice fonts.