It's pretty easy to grow an avocado from the pit. Are there any other trees/plants that can be grown relatively easily from common household fruits or vegetables?
If you find avacado easy, then pretty much anything else will be a cake walk. You can grow pretty much anything you buy in the produce section if it has seeds or a pit.
Pitted fruits have a step you need to perform prior to planting. Place the pit in the bottom back of your fridge where the cold air comes down from your freezer. You know that spot where it just about freezes stuff that's left there too long. Leave it there for 6 weeks, then you can plant the pit or pip of your (peach, apricot, nectarine, cherry, plum, whatever).
For citrus, just plant the seed 1/4 inch deep, put in the sun and keep moist but not wet.
Keep in mind that many fruits will not produce the same fruit you bought. Many fruit raised from seed has fairly unpredictable results, and all the trees that produce you favorite variety of Apple or peach or cherry are actually grown from the scion of a single tree that has been cut and grafted over and over again to the thousands of trees that produce that one Apple or peach. So all those thousand of trees are not just even closely related, they are the exact same tree, just on different roots.
A nectarine is actually a peach that had one branch develop a hairless peach. That branch was grafted to make more of that hairless peach. If you are patient and grow a peach tree from a nectarine pit you might not have a hairless fruit, in fact it highly unlikely. You will also run the chance that you don't like your peach tree's fruit at all and waited 5-7 years just to find that out.
Breeders will take those whips (older seedlings) and graft them to a branch of an adult tree to trick the grafted cutting into producing fruit within 3 years so they don't have to wait so long to find out what they grew.
So it's fun to do anyway, but that why we have breeders and tree producers so we can buy a tree that produces exactly what we want.
May I suggest another couple of trees? We just tried starfruit and Rambutan. They both grew fine, we now have 7 rambutan trees from 9 fruit!!
Since I have been here I have also grown capsicums from market fruit. They are fine, we are harvesting them now. Beans of all kinds grow from market or friend's beans, and tomatillos are also a very safe bet. Get one fruit and fill your garden!
Citrus trees are nice to grow from seeds, and they make great houseplants. Just plant them in soil, water them and wait. I have a grapefruit tree from a seed that I planted about twenty years ago. I planted several, actually, but as seedlings they all got a white, sticky pest that killed all but this one (which survived and has been essentially, if not entirely, pest-free since). I recommend a red clay pot when it gets bigger.
As for plants besides trees, tomatoes, peppers and cucumbers are pretty easy to germinate. For care, they need a lot of light and tend to get pests and diseases easily, though, but they're easy to germinate. They also need more nutrients than a lot of plants. Some pepper varieties take a few weeks, though. Make sure the peppers and cucumbers you use are ripe (green peppers are typically not ripe, although you may get some seeds to germinate still).
You can plant the bottoms of celery stalks and they can grow.
As for legal concerns, you'll probably have a hard time finding out if the varieties they use in the grocery store are patented, and illegal for you to grow. They may also be genetically engineered, unless they're organic.