Just about any type of aquarium safe gravel or sand will work for a substrate. I find the best to be smaller grain so that uneaten food and waste doesn't accumulate between the grains. I would avoid marine substrates and sands as they are calcium based and will mess with the ph of the tank.
One thing to keep in mind is that the filtration is basically working to convert the waste into nitrate. If you understand the nitrogen cycle in a closed system like an aquarium, there's almost zero possibility that you will be able to reproduce the final step of converting nitrate into nitrogen gas. Unless you do not have sufficient filtration as it currently stands, it's unlikely that adding a substrate is going to have any noticeable effect on the water quality. It definitely may look better, but it's not going to substantially reduce the amount of water changes and maintenance to keep the tank clean.
One other thing is that gravel, especially larger size, can trap waste and uneaten food. If you aren't vacuuming the gravel directly when you do water changes, gravel can actually make the tank much less clean than running bare bottom like you currently are. Just make sure if you do switch to gravel, to vacuum the surface to remove waste when you do water changes. A python or other vacuum is the easiest way to accomplish this.
As far as plants, you might be able to get away with very hardy plants like anubias. They're very durable and almost nothing will eat them. As long as the tank is kept at a high enough temperature, there's a chance these could survive in a turtle tank. You could also try plants like water lotus which will send up lily pads to the surface in addition to leaves underwater.