There is a Russian database of WWII war dead that may be helpful to you.

It doesn't have a "random" or "most common" search feature, but if you search with a blank first name, it should give you an idea. For example, here is the beginning of the listings for people with the last name Simonov: http://obd-memorial.ru/html/search.htm?f=%D0%A1%D0%B8%D0%BC%D0%BE%D0%BD%D0%BE%D0%B2&n=&s=&y=&r=

Unfortunately, it doesn't have a filter for gender, so finding women's names among them will probably be difficult.