That’s so funny, I spent about an hour walking around Osaka station the first time I went there trying to figure out how to get out. Ended up back in same place quite a few times. Near the Hankyuu railway staircase.
Somehow I've always done fine at Shinjuku, although during rush hour it can be trickier.