Com Linux, somos gente livre, não somos prisoneiros.
Eu nunca tentei instalar software sem internet, porque não havia necessidade, mas claro que isso é possível. Primeiro, pode-se descarregar os pacotes mesmo com dependências com aptitude. Segundo, pode-se criar espelhos dos repositórios com apt-mirror.
De qualquer forma, é melhor ter acesso à internet por causa das atualizações.
As distribuções Linux, sobretudo as de família Debian, oferecem uma abundância de software, que se instala com poucos cliques do rato o com uma só linha no terminal. Isso contrasta com Windows, onde há muito poucos aplicativos estandardizados e sempre é preciso comprar programas o buscar gratuitos por toda a internet. A segunda diferênça é que os pacotes do Linux dependem um do outro, formando assim um sistema, enquanto no Windows os aplicativos tendem encerrar as dependências. Portanto sim, nós dependemos algo da equipa que forma os repositórios mantendo-os coerentes, e da internet. Mas esta dependência não é absoluta, seria uma questão de comodidade. Pois é possível usar vários repositórios, mesmo espelhos locais, ou até compilar sozinho.
Quanto a TrueCrypt, não sei. Não é livre, ninguem sabe como funciona nem quem o fez. Parece que nunca fez parte de nenhum repositório oficial de Ubuntu (mas sim de Arch, e ainda está lá). Então, o problema com este programa não é espicífica para o Linux. Além disso, o código ainda está disponível na internet.