I've downloaded an LXF file from rebrickable.com. Which software do I need (for Windows and/or Linux) to get the building instructions based on the LXF file?
You probably want Lego Digital Designer:
Once you have the .lxf file open, you'll want to select View -> Building Guide Mode from the menu. This should give you step by step building instructions.
Although lxf files must be loaded with LEGO Digital Designer (LDD), it's not always the case that lxf files are loaded correct/completely with LDD. This because the fact that LDD uses a database where the parts are stored, but it doesn't contain all parts and the database changes from time to time. When trying to load older files, you have about 100% guarantee that the lxf file won't load correct. Thats why i'm using LDRAW and MLCAD. There is though a conversion program to convert lxf (LDD) to ldr/mpd (LDraw/MLCAD). However it relies on a xml file for the conversion. If this file is not complete or correct, the conversion will not be correct.