In soldoni la differenza è che un programma Linux gira su Linux, e uno non Linux no

In realtà la cosa è piú complessa, provo a semplificarla, sebbene mi suoni strano farlo su un forum nel quale si parla di fumetti.
Il computer è una macchina, con una sua struttura particolare, che offre circuiti che fanno cose, e funzioni che permettono di usare questi circuiti (interfaccia degli interrupt). Sulla macchina si può far girare direttamente un programma, volendo, ma le macchine sono ormai estremamente complesse e gestirle bene non è cosa semplice.
Per questo motivo sono nati robi programmosi chiamati sistemi operativi. I sistemi operativi sono dei programmi che offrono interfacce di utilizzo semplice, l'interfaccia delle chiamate a sistema, alle funzioni della macchina. I sistemi operativi hanno poi spesso il vantaggio di girare su piú tipi di macchine (Windows gira su architetture x86, x64 e ARM, GNU/Linux un po' ovunque) dando la possibilità a chi scrive programmi che non abbiano particolari esigenze di girare su piú tipi di macchine diversi senza grandi adattamenti.
Chi scrive programmi, quindi, piú o meno consapevolmente, utilizza le funzioni di interfaccia messe a disposizione dal sistema operativo. Esistono librerie che mascherino le funzioni di sistemi diversi permettendo al programmatore di utilizzare delle funzioni che a loro volta utilizzano funzioni diverse a seconda del sistema su cui si trovano, permettendo cosí con lo stesso codice di fare programmi che girino su sistemi diversi, ma non sempre è possibile.
Un programma per Linux, dunque, è un programma fatto per sfruttare l'interfaccia messa a disposizione da Linux per l'utilizzo della macchina.
Esistono delle interfacce di chiamate a sistema standard, che sono usate da sistemi diversi tra loro, in modo da permettere la creazione di programmi che girino su tutti i sistemi con quell'interfaccia. La piú diffusa è la POSIX, comune a Linux e alle molte distribuzioni Unix, da BSD a Darwin (OS X).