  In several classes of countable structures it is known that every
hyperarithmetic structure has a computable presentation up to bi-embeddability.
In this article we investigate the complexity of embeddings between
bi-embeddable structures in two such classes, the classes of linear orders and
Boolean algebras. We show that if $\mathcal L$ is a computable linear order of
Hausdorff rank $n$, then for every bi-embeddable copy of it there is an
embedding computable in $2n-1$ jumps from the atomic diagrams. We furthermore
show that this is the best one can do: Let $\mathcal L$ be a computable linear
order of Hausdorff rank $n\geq 1$, then $\mathbf 0^{(2n-2)}$ does not compute
embeddings between it and all its computable bi-embeddable copies. We obtain
that for Boolean algebras which are not superatomic, there is no
hyperarithmetic degree computing embeddings between all its computable
bi-embeddable copies. On the other hand, if a computable Boolean algebra is
superatomic, then there is a least computable ordinal $\alpha$ such that
$\mathbf 0^{(\alpha)}$ computes embeddings between all its computable
bi-embeddable copies. The main technique used in this proof is a new variation
of Ash and Knight's pairs of structures theorem.
