I'm ashamed to give the following abstract nonsense answer to this excellent question. Also, this is just an expansion of Santiago's first comment above.
We'll have to talk about morphisms between Lie algebroids over different base manifolds (these are, for instance, the objects of the Lie groupoids they come from). A morphism between Lie algebroids is a linear, bracket-preserving and anchor-preserving smooth map between the total spaces covering a smooth map between the base manifolds. An isomorphism would be composed of two diffeomorphisms.
I am working in the "span picture" and not in the "bibundle picture". I define what a Span of Lie algebroids is, yielding the 1-morphisms of the 2-category Theo is asking for. Let $E_1$ and $E_2$ be Lie algebroids with base manifolds $M_1$ and $M_2$, respectively. A span $E_1 \to E_2$ is a third Lie algebroid $A$ over some base manifold $B$ together with a Lie algebroid isomorphism $A \to E_1$ covering a diffeomorphism $B \to M_1$ and a Lie algebroid morphism $A \to E_2$ covering a smooth map $B \to M_2$. The 2-morphisms are just Lie algebroid morphisms between these "correspondence Lie algebroids". Without having checked all the details, it looks pretty clear to me that this forms a 2-category, with the composition of 1-morphisms the ususal "span composition".
EDIT: One can also make up a version with undirected spans by simply ommiting the condition of being an isomorphism.
Of course, this doesn't answer any of Theo's interesting "$\bullet$"-questions, but principally one could now possibly translate this "span picture" into a "bialgebroid-picture".
Finally, the consistency check: recall that there is a functor from Lie groupoids + smooth functors to Lie algebroids + algebroid morphisms, the latter in the above sense. Applying this functor to spans of Lie groupoids produces immediately a span of Lie algebroids, both in the directed and undirected version.