What Is the Difference between StarkNet Contracts and Cairo Programs?

Cairo is a Turing-complete language that was designed for the purpose of succinctly proving the correct execution of a program (enforcing computational integrity). A Cairo program is stateless, meaning you do not have native access to storage, or to other Cairo programs, nor to the L1 state (although you can access those, as explained below). 

In the Starknet VM, there is a persistent state that smart contracts can access and modify. These smart contracts can store variables, communicate with other contracts, and send/receive messages to/from L1 (read more). StarkNet is an operating system where you can write and deploy smart contracts (written in the Cairo programming language, with some StarkNet-related modification).