It is perfectly true that you do not need to be adding diffused CO2, depending a bit on the plant species and other factors like lighting intensity and nutrients. However, nutrients in general may be lacking, and your observation of no fish providing some of these is accurate. I have a 20g tank that I use only to quarantine new fish acquisitions, and it is planted. It can sit without fish for months, but I do notice an improvement in the plants' appearance when fish are present. Some of this is natural CO2, but more is the nitrogen (ammonia/ammonium) which plants need. Some will occur from organics in the substrate, but the main source is obviously fish.
Having said that, it is still possible to have decent plants, so now we must look into the lighting. If you could detail your light--including type, wattage, duration, spectrum...anything you can--it will help.
Another factor is that plants do take a time to adjust to differing parameters and environments, over usually a period of a couple weeks or more.
The GH of your source water is another factor, as this is the prime source of the "hard" minerals like calcium, magnesium, and a few others. If you could give me the GH (and pH while we're at it). Temperature is fine at mid to high 70's.
Last, what plant species do you have? The large plant in the photo appears to be a sword, Echinodorus species, maybe E. osiris? It is in bad shape, no denying, but we should be able to save it. However, this is a genus of plants that are quite heavy feeders, and adding a comprehensive liquid plant fertilizer is almost a necessity.
Byron.