Need help choosing plants/substrate

There are many plants that will do fine without CO2.
The main purpose of adding CO2 is to push the plants to balance an abundance of light.
Until you find out what your lighting is there is no real definitive way to advise on plants. If you keep your lighting under 3.0 wpg you should not need to supplement with gas.
If you are sure you want to give a planted tank a go, I suggest a clay based substrate such as Flourite. It's more expensive than some, but the long term benefits make it worth the investment now. Use our search engine and type in Flourite for more information on this material.
Plants are not all that difficult or complicated to grow or maintain, and there are a lot of people here who are willing to help you make choices and get your feet wet in the hobby.
I have a 37, BTW and it's my 'show' tank. I think you will like it.

Len

If you have a low light setup around 1-1.5wpg then the following plants are a good choice:

moss, java is the most common
java fern comes in 3 varieties = regular broad leaf, narrow leaf, and frilly (windelov)
anubias comes in many shape and sizes, all of which will do well in a low light, low tech tank
some cryptocrynes like wendtii
anacharis
hornwort

Of the above plants only the crypts benefit from a plant substrate, the rest do not need to be planted and take much of their nutrients from the water. The java plants and the anubias are creeper plants that will attach to driftwood, rock, or gravel over time.

If you want to get a plant substrate for the crypts, check out Flourite, Onyx Sand or Gravel, Schultz aquatic plant soil, and Eco-complete.

With those plant selection keep the lights under 2wpg, do weekly water changes, and you shouldn't need to add CO2 or additional fertilizers.