The functional code for recursively listing feature classes in a geodatabase is provided as ListFeatureClasses example 1 in the help for ListFeatureClasses (arcpy). The topic was also covered in the Recursive list feature classes post at ArcPy Cafe a couple years back.
For your situation, I believe the following code will work:
import os
ws = #path to gdb
arcpy.env.workspace = ws
for ds in arcpy.ListDatasets(feature_type="Feature"):
for fc in arcpy.ListFeatureClasses(feature_dataset=ds):
arcpy.Rename_management(
os.path.join(ws, ds, fc),
os.path.join(ws, ds, '{}_{}'.format(ds,fc[:-3]))
)
The code above will rename what you have already manually renamed.