Here's my best shot at the sort of explanation you're asking for, although it's not nearly as clear as the $2 \times n$ case. The negative sign makes combinatorial proofs difficult, so let's rearrange this as:
$$f(n) + f(n-2) = 4f(n-1)$$
Then you want to show that the number of $n$-tilings, plus the number of $(n-2)$-tilings, is four times the number of $(n-1)$-tilings. (An "n-tiling" is a tiling of a $3 \times 2n$ rectangle by dominoes.)
In bijective terms, then, we want a bijection between the set of $n$-tilings and $(n-2)$-tilings and the set of $(n-1)$-tilings, where the $(n-1)$-tilings are each tagged with the number $1, 2, 3,$ or $4$.
Given an $(n-1)$-tiling, there are three "obvious" ways to obtain an $n$-tiling from it, namely by adding one of the three $1$-tilings on the right end. These generate tilings which have a vertical line passing all the way through, two units from the right end; call these "faulted" tilings, and those which don't have a vertical line in that position "faultless".
So it suffices to show that the number of faultless $n$-tilings, plus the number of $(n-2)$-tilings, is the number of $(n-1)$-tilings. It's easy to see that the number of faultless $n$-tilings is $2g(n-2)$; a faultless tilings must have a horizontal domino covering the second and third squares from the right in some row, and this assumption forces the placement of some other dominoes. So we need $2g(n-2) + f(n-2) = f(n-1)$. Shifting the indices, we need $2g(n-1) + f(n-1) = f(n)$, which you have already said is true.
Have I made any mistakes, and if so, what did I do wrong?
Your recurrences look fine to me.
Also, how can I get the recurrence $a_n = 4a_{n-2} - a_{n-4}$ directly for 3?
To be honest, I think your recurrence is better, since it's more intuitively obvious / less error-prone. :) But to answer your question, here is one way...
Consider the ways to fill the first $2$ columns (of $3$ squares each). There are $3$ ways to fill them using $3$ complete dominoes. So that accounts for $3a_{n-2}$. Besides these, they can also be filled using $2$ dominoes and $2$ half-dominoes, like this
AA.......
BCC......
BDD......
and its reflection. So we need to argue that the number of ways to fill the remaining ... above (incl. the reflected picture) amount to $a_{n-2} - a_{n-4}$ ways, for the desired total of $a_n = 4a_{n-2} - a_{n-4}$.
Now consider any $3 \times (n-2)$ rectangle, which can be filled in $a_{n-2}$ ways. Consider its first column. Either (case A) there are $3$ half-dominoes (no. of ways $= a_{n-4}$), or (case B) there is a full domino plus a half-domino. So no. of ways for case B $= a_{n-2} - a_{n-4}$, but this is exactly the same as filling the ... in the picture, once you consider C+D to be the full domino in that first column of the $3 \times (n-2)$ rectangle. $\square$
Best Answer
I enumerated all $1183$ tilings (not considering symmetry, and not necessarily fault-free). Of those only $6$ were fault-free, and these are in two symmetry classes.
What's your third one?