Condition number of square nonsingular matrix $A$ is defined by
Definition $1$: $cond(A) = \|A\| \|A^{-1}\|$, where the norm $\|.\|$ above could be any of the norms defined for matrices. If we use the usual Euclidean norm on vectors and the associated matrix norm, then the condition number is the ratio of the largest singular value of matrix A to the smallest.
Definition $2$: Condition number for any matrix is defined as:
$cond(A) = \|A\| \|A^+\|$, where $A^+$ is the pseudo inverse of the matrix $A$. Note that for a square non singular matrix $A^+ = A^{-1}$ which implies that Definition $2$ is the generalization of Definition $1$ to find out condition number of any matrix .
As you said, this is very problem dependent and it depends on what kind of accuracy in what quantity you actually want.
Often, $A$ and $b$ contain some measured data (problem coefficients, loads, etc.). They have usually a stochastic nature due to the errors in measurements. What they found later was that instead of $\tilde{x}$ being the solution of $Ax=b$, it solved another problem, $\tilde{A}\tilde{x}=\tilde{b}$, with $\tilde{A}$ and $\tilde{b}$, respectively, very close to $A$ and $b$ in terms of the measurements errors. So instead of solving exactly the already inexactly constructed problem, they found that they solved a still-acceptable problem within the measurement error tolerances even though their computed solution could be considered as a garbage with respect to the original one. But when you have inexactly stated problem, does it have a meaning to attempt to solve it exactly (impossible) or to a very high level of accuracy?
This is the concept of the so called backward error where you seek for what data you actually have the exact solution. It is a very popular topic in numerical linear algebra and error analysis and was pioneered by von Neumann, Turing and further developed and popularised by Jim Wilkinson. This appeared to be an important tool for analysing the rounding errors in floating point computations since the backward error analysis allows you to obtain bounds on the forward errors ($x-\tilde{x}$ in some norm) in two separate parts: the algorithm-dependent part (provide bounds on the backward error) and the problem-dependent part (sensitivity of the problem, some sort of condition number).
If the backward error is small enough (by the order of $\epsilon_{\mathrm{mach}}$, you can say that you solved your problem to the greatest accuracy you could hope for on your computer. Why? Because even if you could somehow obtain "exact" values of the entries of your $A$ and $b$, the relative errors due to their storage in the finite precision arithmetic are of the order of the machine precision.
Now what exactly is the backward error in the context of the linear (nonsingular, for simplicity) systems? Assume you want to solve $Ax=b$ and obtain some $\tilde{x}=x+\delta x$. So you look for $\tilde{A}=A+\delta A$ and $\tilde{b}=b+\delta b$ such that $\tilde{A}\tilde{x}=\tilde{b}$, that is, your $\tilde{x}$ is the exact solution of a perturbed problem. Of course, we would like $\delta A$ and $\delta b$ to be as close as possible to the original data. So consider, e.g., the following formulation:
$$
\eta(\tilde{x})=\min\{\tau:\;(A+\delta A)\tilde{x}=(b+\delta b),\;\|\delta A\|\leq\tau\|A\|,\;\|\delta b\|\leq\tau\|b\|\}.
$$
It can be show that the formula for $\eta$ is actually very simple:
$$
\eta(\tilde{x})=\frac{\|b-A\tilde{x}\|}{\|A\|\|\tilde{x}\|+\|b\|}.
$$
(This result was obtained some time ago in a paper by Rigal and Gaches.)
If you want to have a bound on the forward error, then the following holds:
$$
\frac{\|x-\tilde{x}\|}{\|x\|}\leq\frac{\eta(\tilde{x})\kappa(A)}{1-\eta(\tilde{x})\kappa(A)}\left(\frac{\|\delta A\|}{\|A\|}+\frac{\|\delta b\|}{\|b\|}\right)
$$
assuming $\eta(\tilde{x})\kappa(A)<1$.
Now this bound looks very similar than the one in the question. Note however that the backward error $\eta(\tilde{x})$ can be much lower than what you have as the coefficient by the $\kappa(A)$ in your inequality, that is, the relative residual norm:
$$
\eta(\tilde{x})\leq\frac{\|b-A\tilde{x}\|}{\|b\|}.
$$
At some point, depending on $A$ and $\tilde{x}$, the backward error $\eta(\tilde{x})$ could be even much lower than the right-hand side in the inequality above.
Note that the inequality $\eta(\tilde{x})\kappa(A)<1$ guarantees you that the perturbed system matrix $\tilde{A}$ is nonsingular. In other words, if you'd like to be sure you solved some nearby meaningful problem, you'd like to have $\eta(\tilde{x})$ at least of the order of $1/\kappa(A)$. Also, starting from this point, decreasing $\eta$ by an order of magnitude gives you roughly an additional significant digit in your solution error.
Much more can be said about forward/backward errors, I invite you to have a look on the Higham's book if you want to know more details.
Anyway, if you want to solve $Ax=b$, you need to know that your solution won't be exact no matter what algorithm you use and you always need to ask yourself (or somebody else) what do you expect from your solution and in what terms you want to measure the accuracy. This is sometimes hard to assess even in terms of backward errors since in some cases the classical norms like 2-norm or $\infty$-norm used in rounding error analyses are not exactly what appears in the problem you want to solve.
The typical example of this issue is solving discretised partial differential equations. Often, the forward error norm $\|x-\tilde{x}\|$ nor the residual norm $\|b-A\tilde{x}\|$ have a meaningful role in this context. In practice, one is normally interested in the accuracy in terms of fluxes, that is, the gradients of the discrete solutions. It is not unusual that the errors in fluxes can be much lower than the forward errors in the actual $\tilde{x}$ which has usually the meaning of some coordinates of the discrete functional approximation. Instead of looking at the significant digits of $\tilde{x}$, you want to know whether the error you made by getting $\tilde{x}$ instead of $x$ is somewhat related to the discretisation errors in some proper norm (say, in terms of these gradients). Some sort of accuracy analysis of the algorithms in such a context is, however, still an open, and probably very hard to handle, problem.
Of course, if you really insist that you want to solve $Ax=b$ (even though the exactness of your $A$ and $b$ is at least questionable), you can use some approaches based on arbitrary precision arithmetic. However, this is practical only for some small problems and can be incredibly expensive for larger problems. On some conferences, I saw sometimes people that are working on that (even on, e.g., GPUs) but these kind of solvers are so costly that they're mostly useless for practice. Not mentioning that solving linear problems exactly is at least arguable in any context.
Best Answer
Not really an answer, but too long for a comment. Really a collection of comments...
First, there are many ways of defining condition numbers. All boil down to computing or estimating the worst case sensitivity of a solution to a perturbation in data. A good reference is "Matrix Compuations" by Golub & Van Loan, Section 2.5, "The Sensitivity of Square Linear Systems".
As you noted above, if $Ax=b,Ax'=b+h$, then ${\|x'-x\| \over \|x\|} \le \kappa(A) {\| h\| \over \|b\| }$, and this relationship holds for a norm and its corresponding operator norm.
The point is to have some estimate of the sensitivity of relative errors.
For a given norm $\|\cdot\|_*$ a standard way of defining the $*$-condition number is $\kappa_*(A) = \|A\|_* \|A^{-1}\|_*$. This definition can be used with any norm but the direct relevance to a particular problem (such as above) usually requires that the norms be consistent (that is the matrix norm is the induced norm).
On a finite dimensional space (matrices here) any two norms are equivalent, that is for two norms $\|\cdot\|_a, \|\cdot \|_b$ there are constants $a,b>0$ such that $a \|A\|_a \le \|A\|_b \| \le b \|A\|_a$, hence we have $a^2\kappa_a(A) \le \kappa_b(A) \le b^2 \kappa_a(A)$, so, the condition numbers are also equivalent in this sense.
Just for the record, we have $\|A\|_2 \le \|A\|_F \le \sqrt{n}\|A\|_2$, where $\|\cdot\|_2$ is the spectral norm. Note that $\|A\|_2 = \sqrt{\lambda_\max(A^TA)}$.
Note that the norms $\|A\|_s = \sqrt{\operatorname{tr}(A^TWA)}$ and $\|A\|_2 = \max_{\|x\|_2 \le 1} \|Ax\|_2 = \sqrt{\lambda_\max(A^TA)}$ are equivalent but they are not equal (I'm not sure what frame invariance means, I presume it means rotation invariant, but that is irrelevant here).
So, presumably you are wondering why not just deal with the spectral norm (norm induced by the Euclidean distance)?
The issue is that computing the condition number with the spectral norm is relatively expensive (in addition to computing the inverse), so a cheaper alternative is used if reasonable. Generally it is not required to compute the condition exactly, so a cheaper approximation suffices. (For example, I have seen code where the condition was estimated by computing $\max_k(\|Ax_k\|)$ for a small number of vectors.)
If one is performing computations and the luxury of a condition estimate is available then it gives some 'quantitative' measure of how much relative errors in the input data are amplified and hence a degree of confidence in the results.
And as a complete aside, this illustrates why operations with orthogonal matrices are stable numerically, as we have $\kappa(Q) = 1$ in this case. (Again with the spectral norm.)