I cycled my 75 gallon with plants and had no problems. It at least gives you a pretty tank to look at while it is fishless. The one downside to adding plants first is that at the end of the cycle, with the nitrates so high, you end up with a lot of brown algae. The plants get covered and start to look bad. It will clear up though once you do the water change and lower the nitrates. I added some true siamese algae eaters and they had a feast with mine.
As for decorations, definitely add them. Some bacteria (but not a huge amount) will colonize on surfaces in the tank and the decorations provide another surface.