Many facilities require specific research to be completed before they are unlocked. However, only the Officer Training School is affected by the difficulty level. On Easy and Normal you start with one built. On Classic and Impossible, you cannot build one until your first soldier is promoted to Sergeant.
As far as your inability to immediately build Laboratories or Workshops, they do have a starting requirement of 6 Scientists (for your first Laboratory) or 6 Engineers (for your first Workshop) and you only start the game with 5 of each. Depending on the reward you choose for your first abduction mission, you will be able to build one or the other after successfully completing that mission.
These facilities are always available to be built.
- Access Lift
- Satellite Uplink
- Power Generator
- Thermo Power Generator
These facilities require something to be researched before they can be built.
- Satellite Nexus - Unlocks after you research Alien Nav Computers
- The Foundry - Unlocks after you research Experimental Warfare
- Alien Containment - Unlocks after you research Xenobiology
- Elerium Generator - Unlocks after you research UFO Power Source
- Psionic Lab - Unlocks after you interrogate or autopsy a Sectoid Commander
- Gollop Chamber - Unlocks after you research the Ethereal Device
- Hyperwave Relay - Unlocks after you research Hyperwave Communication
This facility is not like the others.
- Officer Training School - Always Available (Easy/Normal) OR Unlocks after your first soldier promoted to Sergeant (Classic/Impossible)