Why would it be velkeho instead of velky? Is is because the horse is an animate object whereas the tree is an inanimate object?
You are correct, the difference between the two is that one of them is animate and the other one inanimate. :)
Why not "Vidím velký stromy a velkého koně"?
Sorry, disregard the previous. It is one tree. It must be velký strom, stromy is plural.
I find it interesting to discover that trees (and I assume that also grass, flowers, etc.) are considered inanimate from the perspective of Czech grammer. Biologists would strongly disagree ;-)