As you suggest in your question and Todd Trimble mentions in a comment, one interesting choice of morphism between Poisson manifolds is that of a coisotropic correspondence: if $M, M'$ are Poisson manifolds, depending on exactly how you work you either think about coisotropic submanifolds in $\bar M \times M'$, or maps $N \to \bar M \times M'$ with coisotropic image, where $\bar M$ is the same manifold as $M$ but with the opposite Poisson structure (and I give $\bar M \times M'$ the product Poisson structure that you're rightly not fond of). Then it is a straightforward fact that a correspondence $N \subseteq M\times M'$ which is the graph of a smooth map $M \to M'$ is coisotropic in $\bar M \times M'$ iff the map is a Poisson map.
Note that this all generalizes the category in which objects are symplectic manifolds and morphisms are Lagrangian correspondences --- then a correspondence that is the graph of a smooth function is the graph of a symplectomorphic open embedding iff it is Lagrangian. It also has just as many bad properties. Notably, only composition between generic morphisms is defined, as in the non generic case some intersections may not be transverse. So to make it into a category requires the same kind of $A_\infty$ work (or Wehrheim-Woodward method, or...). I know that some of Alan Weinstein's recent papers discuss this category.
This category generalizes easily to the algebraic case that you ask about. Recall that an ideal in a Poisson algebra is coisotropic if it is a Lie subalgebra for the bracket (not necessarily a Lie ideal!), and that a submanifold of a Poisson manifold is coisotropic iff its vanishing ideal is coisotropic. So what I'm suggesting is that if $P,P'$ are Poisson algebras, and writing $\bar P$ for $P$ with the opposite Poisson structure, then one interesting notion of "morphism" $P \to P'$ is a coisotropic ideal in $\bar P \otimes P'$.
Dima Shlyakhtenko has suggested more or less the same category in another answer. There is the following philosophy: Poisson manifolds / algebras are a sort of "infinitesimal" piece of noncommutative algebra, and under this rough relationship coisotropic submanifolds are supposed to correspond to (left, say) modules. Then coisotropic correspondences are roughly the same as bimodules. Recall that from an algebra point of view, bimodules are a fairly natural notion of morphism: they are precisely the left adjoints (say, or right adjoints, or adjunctions) between the corresponding categories of modules. The module theory of an algebra knows a lot about the algebra, including its Hochschild homology and cohomology (and hence its center, its perturbative deformation theory, and so on).
Of course, it is far from the case that the tensor product of algebras has much to do with the (co)product in any category. Rather, remembering only the Morita theory of algebras helps to explain what is their tensor product: it is the tensor product in the 2-category of (nice) categories with left-adjoints as morphisms, in the sense of being universal for "bilinear" maps. One can be quite precise about this: the 2-category of algebras and bimodules is a categorification of the 1-category of abelian groups. Actually, if you remember the underlying algebra, then that's the same as remembering its module theory along with the data of a "rank-1 free module", and so this is a categorification of the 1-category of abelian groups with a distinguished element. (Morita theory is like linear maps that ignore the distinguished element.)
Incidentally, it is now straightforward to invent the notion of "sesquialgebra", which is an algebra object in the 2-category of algebras and bimodules, or equivalently a closed monoidal category structure on the module theory of said algebra. The same notion in Poisson manifolds is an algebra object in the category of Poisson manifolds and coisotropic correspondences, so this includes the Poisson Lie monoids. Alan Weinstein and collaborators a few years ago tried to write down a good notion of "Hopfish algebra" for controlling when this map would be invertible, but my opinion is that their paper doesn't quite get it right. What you should do is the following. Recall that a functor between monoidal categories is strong-monoidal if it comes equipped with a natural isomorphism between the two ways of composing the functor and the corresponding monoidal structures (and maybe extra data for associativity, etc.). A strong monoidal functor between closed monoidal categories also determines a natural transformation between "inner homs", which need not be a natural iso. If it is, call the monoidal functor "hopfish" or "strongly closed". A bialgebra is a sesquialgebra with a marked right adjoint to Vect (equivalently, a marked "rank 1 free algebra", the image of the 1-dimensional vector space under the corresponding left adjoint) which is strong monoidal; a Hopf algebra is a bialgebra in which the strong monoidal functor is hopfish.