Não tenho uma resposta completa pra isso pois, como sempre, cada caso é um caso. Mas note que mesmo linguagens “OO” tem ganhado recursos “não-OO”, o que indica que esses recursos “não-OO” são úteis demais para serem deixados de lado, tornando essas linguagens multiparadigma, como disse o javaflex.
Basta olhar para recursos como lambdas do Java (que são extremamente comuns em linguagens mais funcionais, como Python e Lua), ou mesmo os callbacks que se usa constantemente em Javascript por exemplo (também extremamente comuns em linguagens funcionais e em C, que é comumente descrita como procedural).
Eu te diria pra cursar Ciência da Computação, mas é uma resposta muito longa e cara. 
Primeiro você precisa se perguntar: por que você quer entrar nesse lado mais teórico da computação? O que espera obter com isso? Quais conceitos você tem em mente que quer entender? São só as diferenças e aplicações de paradigmas distintos ou algo mais?
Uma coisa que gosto de reforçar sempre que posso é um bom entendimento de estruturas de dados (pilhas, filas, tabelas hash, árvores, indo até autômatos e grafos, se possível).
Outra coisa que acho interessante é estudar linguagens funcionais. No meu caso, tenho preferência por Lua, pois acho-a menos inchada e complexa que Python (que já é uma linguagem multiparadigma a essa altura).
Abraço.