@eudemonism, I'd say you could have it both ways? With only a small garden available, it needs to be a space that you really enjoy.
I really would encourage you to put in some fruit trees, but in the end it's up to you how important they are. How much work they take is partially dependant on location. If you get fruit fly in your area, the necessary workload goes through the roof. (We only have to worry about birds, possums and codlin moth. And sometimes wallabies..???) Ask at local nurseries which varieties are low maintenance for your area. My parents' garden is in a fruit fly area, and their nectarines, peaches and apples get wiped out by fruit fly; the feijoa tree is OK most years but gets somewhat affected; the orange and lemon trees are fine, because the fruit flies are dormant when they set fruit.
Citrus trees can be very decorative as well as useful. You can get dwarf and "super-dwarf" varieties, they're evergreen, and they have lovely blossoms.
Peas and beans often have pretty flowers. Scarlet Runner Beans (in photo) are particularly nice, and have a soft perfume too. Once planted, they'll come up from the roots every year for 5-10 years, so best to plant them where they'll have a chance to do so.
A lot of herbs are also great landscaping plants. Tulbaghia (Society Garlic) is a flowering perennial often planted as a drought proof ornamental, but as the common name suggests, it's also an excellent source of garlic flavouring. Garlic Chives also have pretty flowers. Rosemary can be clipped into a hedge or allowed to grow into a bush, and nowadays there's blue and pink flowered varieties to choose from, and also prostrate ones that can be planted to cascade over walls. Sage has nice grey leaves and short lived blue flowers, but you can also get ones with variegated or purple leaves. (I've found the purple leaved one to be one of the tougher ones.) If you don't get too much frost, Pineapple Sage gets gorgeous red flowers, and tastes good too.
Lemon Verbena is a pretty shrub with intensely lemon scented and flavoured leaves. Lemon Grass is just as good as a lot of the ornamental grasses, but doesn't grow well where I live. (Too many winter frosts.)
Coming from the other (ornamental) direction... some highly perfumed roses would give you rose petals to use in Middle Eastern or Indian recipes, and I often add petals to fruity recipes- jams, cordials, icecreams. A Google search shows up a lot of recipes. You'll also get a lot of results if you google "edible flowers", and "edible Australian natives" or "bush foods".
So... if you designed a garden around edible ornamentals and ornamental edibles, then filled it out with a veggie bed or two for the tasty but not so ornamental vegs, and a few favourite "must have" pretties?
