Pomegranate comes to mind. Really nice show of flowers in the spring, can be left as a bush or pruned to tree form, few pests or diseases, but does drop it's leaves in the winter. Pineapple guava is really an attractive small tree, but you'd have to check on how well it would do in Houston. Very desirable fruit, pretty much trouble free plant.

Never had Pineapple guava before. I will have to try this. Many thanks for the suggestion.

I recommend a FUYU perssimon. Beautiful tree. Mine is 10 years old and only 15 feet tall.

The fruiting dogwoods may be a good option. Both the Cornus kousa variety and the cornelian cherry variety are naturally small in stature, beautiful like the more traditional dogwoods, and make an edible fruit. Mine haven't started bearing yet - they are still young - but I planted them where I planted them as fruiting ornamentals.

Citrus would be the best, with the deep green leaves, showy and fragrant flowers and the fruits.

Kumquat is best in the citrus family, if you like the fruits.

I've seen old fig trees that have been pollarded so often that they are very pretty when they no longer have leaves in winter. Trifoliate orange and plums are small and nice when in flower and fruit. Weeping mulberry or a dwarf form. A dwarf peach or nectarine tree is BEAUTIFUL in full bloom, as are some of the pink-flowered plums and apples.

Quince? Allegheny Serviceberry? Didn't notice you said "non-deciduous."...that limits you a bit.

Strawberry and lemon guava are evergreen, much more cold tolerant, stay small and have delicious fruit. Cherry of the Rio Grand and its relatives are evergreen, make a great hedge plant and can be trimmed to whatever height you want. They look very much like Eugenia, which they are related to.

We just uprooted a tropical pink guava because the fruit tasted awful and it had these big hard seeds that were hard to separate from the flesh. Another forum explained that the strawberry types are like that. The tree is (was) very pretty. The other forum told me to get a pineapple guava. Almost seedless and very tasty. Well, we are done with guavas, and are planting a Bearss Lime in it's spot today.

Actually, most fruiting trees can be kept small if you do the work to prune them right at summer solstice. Pruning while they are dormant in the winter makes them grow busher, while doing it while they are in peak growing keeps them small.

Not sure about Dallas or evergreens though.

All fruit trees can be kept small with trimming but summer solstice has nothing to do with it. You trim after all the fruit has finished, whenever that happens to be. You can also trim at any other time of the year to help keep the shape and good "scaffolding" branches. Just make sure to learn about the fruiting habits of the specific tree to be sure you are not cutting off all the wood that will produce fruit. See the Dave Wilson Web site for great info on this.

Look up white sapote. I have several, keep them small with pruning, is evergreen, beautiful foliage. Fruit does not travel well hence many people have not had the opportunity to be delighted by their taste. Unusual, beautiful, and a fruit that's out of this world good. Can take any frost you may receive in your area. Evergreen.

And a side note: Attracts the Giant swallowtail, whose larvae use the tree's leaves. They use a very small amount, and never even 'dent' the leaf or fruit population.

Landscapers usually do not recommend pomegranate as an ornamental tree because of its irregular branching/leaving habit, and their tendency to sucker by the root. I so wanted a pomegranate to work for the same purpose as you, but I think I've talked myself out of it.

A permission would look gorgeous, but might grow too tall for what you're looking for.

I'd plant a citrus - I'm jealous that you live in a region where that's possible.

kumquat is a good choice

Cornus kousa I'd consider only marginally edible, too bland and insubstantial. Cornus mas, though, is a fine fruit: too tart and astringent (quite like a cranberry) to be enjoyable out-of-hand, but they make a memorable raisin if you pit and dry them at 135F overnight. They also attract yellowjackets here in New Jersey, who become drunk on the fallen fruit and unable to fly.

Loquat...evergreen, fruit in May-June and flowers in Winter

Carub....evergreen flowers and ripe fruits in fall

Olive....one of the most ornamental evergreen plants, fruits in oct-nov...easy to transform them in table-olives

Yes, pomegranates are so ornamental–both the flowers and fruit–that even if you don't like eating them this is still a plant people might want consider for their yard. It grows well in warm dry climates.

vm3y, pomegranates grow almost more like a shrub than a tree, especially some of the varieties, and they can be cut back and managed like a bush too. They'll only get unwieldy if you let them.

Another one I can think of are certain types of crabapples, flowering peach.

Some ornamentals, such as flowering quince and Japanese plum blossoms produce fruit that is clearly inferior to the varieties that were bred for eating, so to some extent there can be a trade-off between attractiveness of the blossoms and tastiness of the fruit.

Medlar has just average attractive blossoms, and just average tasting fruit, it could be seen as a sort of compromise.

Mulberries make for very attractive trees, they produce beautiful foliage. A little fact some people do not know, the leaves from the Mulberry tree can be eaten too, or fed to livestock.

For those that live in the much warmer parts of the country, why not plant a banana instead of a regular palm? You can use the banana leaves to cook with too. Bananas can be grown in most of Southern California, parts of Texas, the Gulf coast, and Florida. Basjoo, Sikkimensis, and Blue Java tend to be hardier than the others. For those in South Carolina, because of the shorter warm season, Viente Cohol may be a better variety if you want to be able to get any fruit (but it may need some winter protection).