Jodo lauser, mira que le he dado vueltas y la has clavado. Bueno, solo faltaba añadir "categoria=" después de index.php
Código:
<IfModule mod_rewrite.c>
RewriteEngine on
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*)$ index.php?categoria=$1
</IfModule>
No se, había probado cosas muy similares, pero supongo que no lo ponía del todo bien. En cualquier caso, muchísimas gracias.