We have three pairs of those in our garden area. Their roots are shallow, perhaps, but they can be long. I'm constantly pulling up nascent aspen groves thirty, forty, or fifty feet from the trees we have. And occasionally I hack at the roots to make a little more space for roses. The trees were a little unhappy last year about it. And when DW complained about this unhappiness I decided to maybe hack a little less assiduously. Ours really are essential to the garden.
Anyway, congrats on ridding your garden of both an eyesore and a source of extra labor. Alexander Mackenzie would get pretty big if you were looking for a cold hardy, easy to grow rose. So would Highdownensis. But I expect a nice crabapple like Brandywine might be even better.
I absolutely love golden rain trees; but when I grew one in NJ, I kept moving it around because as beautiful as its flowers were, they clashed with every rose I grew in the garden, even the yellow and red ones.
