I know there may be issues with libraries from one OS not being available for another, like say Android and Ubuntu, but can programs from one or the other OS run on the other without recompiling?
If a Linux OS is still Linux, shouldn't it be able to work as intended? And does the issue of the CPU\GPU being different have an effect as well?
This may be off topic for SO, but I found this on Ask Ubuntu
Is linux binary universal to all kinds of distributions?
This is two questions:
Is a Linux binary universal to all distributions?
It depends:
If the program is using nothing outside the Linux kernel, it will be universal except for the 32- or 64-bit question. A Linux "hello world" (a minimalistic program that just prints "hello world" to a terminal window) could probably be independent of the distribution. If the program is using any non-kernel library or service (which is most of Linux, the kernel is fairly small), there are differences in which libraries are included, which versions these libraries are and where they are located. So in this (most common) case distributions are not equal. Why do many commercial programs say that they only work on one or a few distributions?
Because there is a very large number of Linux distributions, and nobody wants to test their program on all of them.
A commercial vendor will normally say that they support only the distributions they have tested their software on. It may or may not work on other distributions, from the vendor's perspective the point is just that you can't complain if it does not work on a distribution they don't support.
Which distributions are selected for testing depends on what the vendor expects their customers to be using. Commercial/professional programs commonly pick enterprise distributions, possibly through a reasoning similar to "people who paid for their OS are more likely to pay for our software", possibly simply by counting the distributions used by their existing customers.
See also Mark Shuttleworth (the guy that is the reason we have an Ubuntu in the first place) on binary compatibility between Ubuntu and Debian - Debian is the closest distribution relative of Ubuntu.