Let us remember the definition of faithful, transitive and free:
The action of a group $G$ on a set $X$ is called:
Transitive: if $X$ is non-empty and if for any $x,y\in X$ there exists $g\in G$ such that $g\cdot x = y$.
Faithful (or effective): if for any two distinct $g,h\in G$ there exists $x\in X$ such that $g\cdot x \neq h\cdot x$; or equivalently, if for any $g\neq e\in G$ there exists $x\in X$ such that $g\cdot x \neq x$. Intuitively, in a faithful group action, different elements of $G$ induce different permutations of $X$.
Free: if, given $g,h\in G$, the existence of $x\in X$ with $g\cdot x = h\cdot x$ implies $g = h$. Equivalently: if $g$ is a group element and there exists an $x\in X$ with $g\cdot x = x$ (that is, if $g$ has at least one fixed point), then $g$ is the identity.
Now we can determine your three group actions:
The action of $S_n$ on a set of $n$-elements is as you showed transitive. It is also faithful as you explained, but it is not free, because there are elements on $S_n$ that do have fixed points that are not the identity, for example $1\to 1, 2\to 3, 3\to 4, n-1\to n, n\to 2$. Since the action is transitive the group of orbits is the group of one element.
The action of $O(n)$ on $S^{n-1}$, it is transitive, since there is always a rotation that can send any point of $S^{n-1}$ onto the north pole. For $n>2$, It is not free since for any point on $S^{n-1}$ there are many rotations different from the identity, whose axis of rotation is the line that passes through that point and the origin, and all of these fix that point. It is not faithful neither since any element of $O(n)$ that is not the identity moves $S^{n-1}$, therefore there exists a point on $S^{n-1}$ that is not fixed by the action. Since the action is transitive the group of orbits is the group of one element. The case $n=2$ the action it is transitive, free but not faithful.
The action of $O(n)$ on $\mathbb{R}^n$ is not free since every element of $O(n)$ fixes the origin but is not necessarily the identity. It is not transitive either, since for two elements of $\mathbb{R}^n$ whose length are not equal, you cannot find an element of $O(n)$ that sends one on the other (the elements of $O(n)$ preserve norm). It is not faithful neither since when you restrict the action to $S^{n-1}$ it is not faithful either. Since $\mathbb{R}^n=[0,\infty)\times S^{n-1}$ the set of orbits can be identified with $[0,\infty)$ since when $O(n)$ is restricted to the second factor it is transitive.
Edit: I didn't notice that $m$ and $n$ were different.
Let's deal with the case $n=m$ first, as it gives you the right idea for the general case.
Since $P$ and $Q$ are invertible matrices, and you are running over all of them, you may replace $P$ by $PQ$. Then you are looking at $PQAQ^{-1}$. You might as well replace $QAQ^{-1}$ by $A$ because in the end you are likely to want a description that is independent of basis anyway.
So now, you want to find some invariant that distinguishes matrices apart that is not affected by multiplication by an invertible matrix. Once you have done that, then you want to decide if any two matrices with the invariant are related by multiplying on the left and right by invertible matrices, or equivalently as I have shown, a change of basis and a single multiplication.
First, what is the orbit containing $I$?
So once you look at the case $m=n$, you see that you want to use the one matrix to obtain a normal form of some sort, and then you can take transposes to push the 'adjustment' matrix to the other side and take normal forms again. The obvious one to do in general is Gaussian elimination, as that is more or less the only thing we can do with arbitrary matrices.
Best Answer
Since the group generated by the two matrices $$ a= \begin{pmatrix} 1 & \lambda\\ 0 & 1 \end{pmatrix},\ b= \begin{pmatrix} 1 & 0\\ \lambda & 1 \end{pmatrix},\ \lambda\in\mathbb{R}, \lambda\geq2, $$ is a free group, the corresponding action of the free group on $\mathbb{R}^2$ is faithful.