Would "Kde toho psa vidíš?" be correct also?
Yes, it is correct and accepted.
Should "Kde vidíte ten pes?" Be accepted?
Pes (dog) is an animal, so its accusative singular is not pes but psa, like the genitive. This also applies to toho.
Not really there should be "toho" instead of "ten", because it's accusazive of an animate masculin.