When I started riding a few years ago, I had a "wide, soft, cushy" seat on my new bike. I had a MISERABLE time of things -- like you describe. Sitting on anything was HORRIBLE, and it was a tailbone thing like you describe.
My solution was a smaller, firmer saddle. That one hurt for a while too -- there's a certain amount of getting used to being on a bike for any distance, but it was a whole different kind of ache, and I toughened up after bit. Maybe that will work for you too!
Karen in Boise