If you have not ridden much before, there is always going to be some soreness. Your backside does toughen up with more riding. As for saddle suggestions, it is a personal thing. Generally, the more upright you sit, the wider the saddle needs to be. A cushy seat might seem more comfortable initially, but on a long ride it can end up being too soft. Shape is by far the most important thing. Some brands and shops have trial saddles or satisfaction guarantees.
Some people have an aversion to spandex cycling shorts, but they make riding more comfortable than even casual-style cycling shorts, and certainly more than regular shorts.