Is it possible to change your character's appearance and/or gender after leaving Goodsprings? I'm playing on PC

Only with mods, unless you join The Kings, but they only have a barber.

There are mods that add plastic surgeons or plastic surgery options to medics, and also there's a facial reconstruction machine thingy in the Underground Hideout mod.

There's a console command on the PC that'll let you change your appearance.

You can use the console commands showracemenu and showbarbermenu from FO3 to access the menu's, but that may (or may not) mess up the game in other ways (so I've read). So use at your own risk.

Maybe in Old World Blues. There's a machine or something that lets you modify your character sheet; it's possible there will be a plastic surgery option, too. Just a guess.