I would say that first-order-logic has a data complexity and a formula complexity.
Data complexity: fix the theory and let the structure vary and measure complexity in the size of the domain of the structure. Complexity is exponential.
Formula complexity: fix the structure and let the formula vary and measure the complexity in the size of the formula. Complexity is exponential but because formulas are written by humans, it has probably an upperbound of 4 in real life.
EDIT: Try to explain better.
I follow an introductory course on FO logic. A question on the exam was: "What can you say about the complexity of FO in half a page?". The professor said it was a trick question.
I tried to identify a problem in first-order-logic with the highest complexity (a problem that I have seen in the class). Lets say FO finite model checking.
This problem has as input a finite structure S and a FO sentence e. Deciding whether S satisfies e is polynomial in the size of the domain of S and exponential in the size of e.
When measuring the complexity, we can fix the theory and let the structure vary and measure complexity in the size of the domain of the structure (data complexity).
Alternatively, we can fix the structure and let the formula vary and measure the complexity of the inference problem in the size of the formula. (formula complexity).
There are algorithms for finite model checking using relational algebra that are exponential in the number of quantifier alternations ∀∃∀∃. In practice, this number is always low. Probably an upperbound of 4.
If the domain contains $n$ elements and the formula contains $m$ variables, then the truth table should be no larger than $n^m$. And if this is what you mean by this question, this would imply that your second statement makes sense and the first statement is under question.