Yeah it really doesn't count if the male and female character choice are two different characters.
Mm. That'd leave the Summon Nights still there, then, of the ones I've played recently (and can recall, anyway). They do a pretty bang-up job with dialogue shifts, iirc. Less so regarding mechanical changes (read: There kinda' aren't any.), but eh.
And @Eyetwo, I think Neo, at least, is thinking about games where genderflipping the same character (the MC, in most cases) has a notable difference. I'd personally expand consideration beyond that (as should be obvious given the response

), but it's fair enough to consider that as a separate consideration from games that let you choose between different gendered characters instead of simply choosing the gender of a particular one.
For that, the Gearhead games are probably about in line with the Fallout ones, now that I think about it. So there's two (Well, technically five -- SN goes for 3 games on the GBA, Gearhead has 2 on the PC) more to add to the list.
E: Oh! And I'm fairly sure some of the Super Robot Wars games have that going on, too, if my memory isn't failing me. Pretty sure a handful of 'em let you choose gender along with robot type, with all sorts of effects.
E2: And there's a fair number of CYOA or text based adventure games out there that exhibit the effect, of course. There's actually someone LPing one over in the Play with your Buddies right now.