Hi Steve; I live in West Yorkshire, and I have been slowly transforming my garden into a more permaculture space over the past four or five years. Like your wife, my husband was at first reluctant to give up our substantial lawn, and we also have a little boy who likes to play football. Rather than completely take out the grass altogether, I have been chipping away at the edges gradually over these years; every year I add a new bed, extend a bed, or plant a tree. And I always consult my husband before I make a change like this; after the first few years of growing our own food, he has been converted. He even told me last year that if I wanted to completely replace the lawn with food growing beds, he'd support me completely!
But I have found our lawn is actually a benefit for our particular food growing system: it's a great food supply for our flock of chickens, who get to rotate throughout sections of it, reducing our need to mow, fertilise, and weed it. And our climate waters it for us too

However, if you have foxes (we don't) this might not be a good option; my inlaws lost their chickens to foxes, one by one, in their garden in London--not in the secure coop at night but in broad daylight out on the lawn. Another reason the lawn works for us: we have a mature conker tree in the back corner of our garden, and grass is a good option for the shade where not much else will grow; that shady area is growing eggs, and meat too.
As far as children go, we have found that having different shrubs and trees and other permanent fixtures around the garden is much more fun to play in than a plain old lawn. Our son, aged 5, can explore, hide, spy on the neighbours, climb, dig, play with chickens, "fish" in the pond, etc; it's like a playground with all kinds of different levels and activities. He can play football at the local park, or out on the street with the neighbourhood children, though I appreciate this may not be an option for you if you live on a busy road.
Like you, I also have a fairly good sized south-facing garden, and I have the following trees, all dwarf or semi-dwarf: 2 varieties of apple, 1 pear, 1 sweet cherry, 1 morello cherry, 1 almond, 1 plum, 1 fig. I also have the above-mentioned conker tree, a hawthorne hedge, a living willow fence, and a few alders (N-fixers) kept at shrub size. Most of my trees are grown at the edges of my property, either against the eastern fence, or near the house, so as to limit the shade they cast on the beds. My fruit trees, at the back of my borders, are planted alongside ornamental and edible shrubs like hydrangeas, roses, currants, berberis, etc, to give a more landscaped look; towards the front of my borders I have some herbaceous plants like peonies, lupins, campanula, and my annual vegetables, planted in drifts. I actually have some bedding too, like calendula, nasturtiums, pansies.
I guess what I'm trying to say is, it's possible to make an attractive garden which also provides food, habitat, and space for people too. I highly advise reading Gaia's Garden by Toby Hemenway, if you haven't done already. For ideas on garden design, get a hold of some garden books or magazines, and see how professional designers lay things out; it's easy to subsitute edible and wildlife friendly plants into ornamental schemes. In your case, I would concentrate on converting your borders now, and doing a little at a time. And those "ornamentals" usually have plenty of value in a small garden anyway: early flowering shrubs like forsythia provide valuable nectar and pollen to bees when there's not much else around; thorny rambling roses provide excellent cover and nesting places for birds, as does ivy and clematis--so don't be in a rush to get rid of anything just because it's ornamental.
Good luck!