For example, if $x$ is 1 billion, the smallest possible $a \times b$ will be $3 \times 19 = 57$.
This is because:
$2^{30} \ge 1000000000$
$2 \times 30 = 60 $
$3^{19} \ge 1000000000$
$3 \times 19 = 57 $ (← $57$ is the smallest)
$4^{15} \ge 1000000000$
$4 \times 15 = 60 $
$5^{13} \ge 1000000000$
$5 \times 13 = 65 $
$6^{12} \ge 1000000000$
$6 \times 12 = 72 $
So, I did it by trial and error.
But is there a formula to calculate $a$ and $b$ for an arbitrary $x$ (e.g. 200 thousand or 1 trillion)?
Hint: Assume $a, b \gt 0$. The product $a \times b$ will be minimized when both $a$ and $b$ are made as small as possible. Since the inequality $a^b \ge x$ implies $a \ge x^{1/b}$, the best we can do is to minimize $b \times x^{1/b}$. The result (via derivatives) gives an equation for $b$ and thus the lower bound on $a$. Setting $a$ exactly to the lower bound and multiplying this by what you found for $b$ will give the smallest possible value of $a \times b$ subject to the constraint.
Detailed Solution: Letting $y=b\times x^{1/b} = be^{\frac{1}{b}\ln x}$ the first derivative with respect to $b$, and holding $x$ constant is:
$$y'=(1-\frac{1}{b}\ln x)e^{\frac{1}{b}\ln x}.$$
Setting this to zero and solving for $b$ in terms of $x$ gives $b=\ln x$. We can verify that setting $b$ to this value gives a minimum value for $y$ by calculating the second derivative which is:
$$y''=\frac{1}{b^3}e^{\frac{1}{b}\ln x}(\ln x)^2.$$
Since the second derivative is positive for all $b>0, x>1$ (more on this later), its clear that $y$ is concave up at the critical value of $b=\ln x$. Graphing $y$ as a function of $b$ for various values of $x$ shows that the function is concave up and reaches its lowest value when $b=\ln x$. Also, the above implies a new restriction on $x$ to be greater than $1$ so that $b=\ln x > 0$.
Now that we've found $b$, lets take a look at $a$. Since $a$ is constrained from below by $x^{1/b}$, setting $a$ exactly to its lower limit and simplifying gives:
$$ a = x^{\frac{1}{b}}=x^{\frac{1}{\ln x}}=(e^{\ln x})^\frac{1}{\ln x}=e \ \text{(nice surprise!)}$$
Therefore $a\times b$ will be minimized subject to the constraint when $a=e$ (in every case!) and $b=\ln x$.
Integer Solutions
It looked like you were working strictly with integer values of $a$, $b$, and $x$. The above approach does not assume that restriction. In fact, you'll find that the minimum product, when $x$ is 1 billion, is a little bigger than 56.3. The values for $a$ and $b$ are about 2.72 (now determined to be $e$) and 20.72 ($\ln x$) respectively. All pretty close to what you found but with a slightly smaller minimum product.
Algorithm for finding optimal integer factor pairs
Find the optimal solution assuming both $a$ and $b$ can take on real values. This is outlined above where $a=e$ and $b=lnx$. Let $A = a \times b$.
Round $A$ up to the nearest integer and call this $A^*$.
For each pair of integer factors $a^*$ and $b^*$ such that $a^* \times b^* = A^*$, test $a^*$ and $b^*$ against the constraint, for given $x$.
Keep the pairs $(a^*, b^*)$ that satisfy the constraint.
If all factor pairs for $A^*$ have been tested and none have been found to satisfy the constraint, then set $A^* = A^* + 1$ and repeat the process starting with step 3.
If at least one factor pair has been found to satisfy the constraint then the set of all pairs found are the best integer solutions to the original problem. Specifically, each pair $(a^*, b^*)$ found gives a product $A^*$ that is as close to the minimum product $A$ as possible while satisfying the constraint and the need for integer solutions.
Examples
Below is an example when $x=32$. For the case when both $a$ and $b$ can take on real values, their optimal values are shown as the intersection of the horizontal and vertical blue lines. Their product $a \times b$ is 9.42. Thinking of their product as an area, also plotted is the curve of constant minimum area which passes through the intersection of the blue lines and, as we'll see, forms a boundary for integer solutions.
To find integer solutions $(a^*, b^*)$ that get as close as possible to the minimum area, we round up 9.42 to 10 and then test all the factor pairs of 10. These are shown as points plotted on the graph along with the product of the pair. These points fall above the curve of constant minimum area, though scaling may give the impression they are on the curve (they are not). The specific integer factor pairs that satisfy the constraint $a^b \ge x$ are plotted in red and in this case the best integer solution is (2, 5). Depending on $x$ there can be more than one pair that satisfy the constraints.
A second example is the specific one given by the OP where $x=1,000,000,000$.
The optimal real-valued solution is the intersection of the blue lines and the best integer-valued solution (3, 19) is shown as the red point.
Notes:
This algorithm does not necessarily minimize the number of steps required to find integer solutions. Starting with the optimal real-valued solution and working up is a good start, but there may be other shortcuts.
In some cases there are multiple integer solutions for a given x. These solutions tend to hover around the optimal real values for $a$ and $b$.