Are there "small" machines which can efficiently match regular expressions? It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially exponentially larger. Furthermore, given a string $s$ and a regular expression $r$, the NFA can test membership in time proportional to $|s| \cdot |r|$, and the DFA can test membership in time proportional to $|s|$. The slowdown for the NFA arises from the fact that essentially we need to track the sets of possible states the automaton could be in, and the exponentially blowup for the DFA arises from the fact that its states are elements of the powerset of the states of the NFA.

Is it possible to efficiently (ie, in time better than $O(|r| \cdot |s|)$, and space better than $O(2^{|r|})$) recognize regular expressions, if we allow using more powerful machines than finite automata? (For example, are there succinctness gains to recognizing regular languages with pushdown automata, or counter machines?)
It's easy enough to trade off time for space, as follows.

Convert the regular expression to an NFA — for concreteness in comparing algorithms, we'll assume that $r$ is the number of NFA states, so that your $O(rs)$ time bound for directly simulating the NFA is valid and your $O(2^r)$ space bound for running the converted DFA are also valid whenever you're working in a RAM that can address that much memory.

Now, partition the states of the NFA (arbitrarily) into $k$ subsets $S_i$ of at most $\lceil r/k\rceil$ states each. Within each subset $S_i$, we can index subsets $A_i$ of $S_i$ by numbers from $0$ to $2^{\lceil r/k\rceil}-1$.

Build a table $T[i,j,c,A_i]$ where $i$ and $j$ are in the range from 0 to $k-1$, $c$ is an input symbol, and $A_i$ is (the numerical index of) a subset of $S_i$. The value stored in the table is (the numerical index of) a subset of $S_j$: a state $y$ is in $T[i,j,c,A_i]$ if and only if $y$ belongs to $S_j$ and there is a state in $A_i$ that transitions to $y$ on input symbol $c$.

To simulate the NFA, maintain $k$ indices, one for each $S_i$, specifying the subset $A_i$ of the states in $S_i$ that can be reached by some prefix of the input. For each input symbol $c$, use the tables to look up, for each pair $i,j$, the set of states in $S_j$ that can be reached from a state in $A_i$ by a transition on $c$, and then use a bitwise binary or operation on the numerical indices of these sets of states to combine them into a single subset of states of $S_j$. So, each step of the simulation takes time $O(k^2)$, and the total time for the simulation is $O(sk^2)$.

The space required is the space for all the tables, which is $O(k^2 2^{r/k})$. The time and space analysis is valid on any RAM that can address that much memory and that can do binary operations on words that are large enough to address that much memory.

The time-space tradeoff you get from this doesn't perfectly match the NFA simulation, because of the quadratic dependence on $k$. But then, I'm skeptical that $O(rs)$ is the right time bound for the NFA simulation: how do you simulate a single step of the NFA faster than looking at all of the (possibly quadratically many) transitions allowed from a currently active state to another state? Shouldn't it be $O(r^2 s)$?

In any case by letting $k$ vary you can get time bounds on a continuum between the DFA and NFA bounds, with less space than the DFA.