solving $f(f(x))=g(x)$
Q1: No. Let $g(0)=1, g(1)=0$ and $g(x)=x$ for all $x\in\mathbb R\setminus\{0,1\}$. Assuming $f\circ f=g$, let $a=f(0)$, then $f(a)=1$ and $f(1)=g(a)=a$ since $a\notin\{0,1\}$. Then $g(1)=f(f(1))=f(a)=1$, a contradiction.
Q2: No. Let $g(x)=-x$ or, in fact, any decreasing function $\mathbb R\to\mathbb R$. Then $f$ must be injective and hence monotone. Whether $f$ is increasing or decreasing, $f\circ f$ is increasing.
Ulm invariants.
Surely someone still knows this? Given $f \colon A \to A$ and $g \colon B \to B$, is there a bijection $\phi \colon B \to A$ such that $f(\phi(x))=\phi(g(x))$? There is a system of cardinal numbers, the Ulm invariants, associated with $f$ so that the answer is ``yes'' if and only if $f$ and $g$ have the same invariants.
If $f$ is bijective, then the Ulm invariants are just counts of how many cycles of each size there are (including the infinite cycle size modeled by the integers with $n \mapsto n+1$).
But when not bijective, the system of invariants is more complicated. You need to count how many points map to each fixed point, and how many points map to each of them, and so on. And similarly for cycles of other sizes. But I cannot tell you the details, and this box is probably not the right place to do it anyway.
So for a solution to the problem, consider what the Ulm invariants of $f(f(x))$ are in terms of those of $f$. Then compare to the Ulm inveriants of $\cos$. Or whatever you want to get.
Ulm himself may have originally done this to study isomorphism of abelian groups. Taking products, reduce to the case of a $p$-group for a given prime $p$, then your map for study is $x \mapsto x^p$. Or something like that. Ulm invariants may also be given to characterize up to isomorphism linear transformations (on possibly infinite-dimensional vector space).
Q2) has a negative answer. Namely, if, e.g., $g(x)=-x$ for all $x\in\mathbb{R}$, then there is no continuous $f:\mathbb{R\rightarrow\mathbb{R}}$ such that $f\circ f=g$.
As to Q3, see, e.g., Theorem 3 in http://yaroslavvb.com/papers/rice-when.pdf.