East side of the house? Then the house would shade them in the afternoons . .. they might even get runoff from the roof, too.
How about a pergola and a fast-growing vine like a passionvine or Sky vine? That would give you fast shade without too much fuss and bother while you wait for the new trees to grow. Think about how much you'll save on your a/c bill once you get some shade around that house!
