I'm looking for a medium sized deciduous shade tree to plant in Phoenix, Arizona to shade part of my house. It needs to be deciduous so that it will let the sun through in the winter and provide shade in the summer. The tree does not need to be indigenous but will obviously need to be able to withstand harsh summers. Also, preferable would be something that grew fast so as to provide maximum benefit as soon as possible.
Try Arizona Ash (Fraxinus velutina). This tree fits with all of your needs, except for size. It gets 30-50' high and spreads 30-50'. It is a good shade tree, it is wind, drought, and heat resistant, grows rapidly, looks good, and has good yellow fall color. Good in any soil. Fraxinus velutina 'Fan-Tex' is similar. It gets 30-50' high, 30' wide, and grows well in the same conditions. These are both very shady in summer. Desert ironwood (Olneya tesota) is very tolerant of desert conditions, and is smaller.