Did the trees flower over the last few months? Do they currently have small green fruit on them? If so then you have a chance to save the current crop in which case you should definitely fertilise. Use a good quality citrus fertiliser. For trees of that size you will need to apply quite a bit. It has taken me a few seasons of caring for the established citrus trees I moved into a place with to get my head around how hungry they are. Without enough fertiliser you will get a lot of fruit drop.
If you don't have fruit on your tree now then you've missed this seasons crop so fertilising or not won't make a huge difference, but it can't hurt.
You should definitely clear all grass and weeds in the area under the trees. Citrus do not like grass etc growing in the root zone. Be careful when removing the weeds as citrus have relatively shallow roots than can be disturbed by vigorous digging. Once you've cleared the root zone, put down a goodly layer of cow manure (and fertilizer) then top with mulch such as sugarcane or lucern.
Yellow leaves can be a sign of general nutrient deficiency (lack of fertiliser) or specific lack of zinc and magnesium. First thing is to clear the weeds, mulch and fertilise. If you still have problems you can investigate further.
The other thing you probably want to do it give them a good prune. If they have fruit on them just take off the worst looking leaves and any dead wood at this point. If not, then you could take the opportunity to prune them harder, in particular opening up the middle of the tree and removing any diseased leaves (leafminer, black scale etc). My established citrus have been doing much better since I gave them a hard prune after I suspect several years of no pruning. Just avoid doing this while they are fruiting or you will lose that crop (most likely).
In general, citrus need a fair bit of TLC to keep them going well. I'm in northern Sydney and find that unless I keep up a consistent schedule of applying white oil then leafminer and black scale take over. I also get a lot of bronze sucking bugs (commonly known as stink bugs) which I remove with a pair of tweezers. Again I find that unless I go around at least once a week or so the bug population gets out of hand. Personally I'd find it difficult to give this attention to a 4 metre high tree, so I now keep mine to around 2-2.5m high. This obviously makes picking the fruit much easier as well.