@HebaruSan I only deploy up on this particular build, and just to shorten the mission a bit by adding a little drag and also to slow the descent a bit and keep it from accelerating too much (basically as a poor man's drogue chute) as it comes back down. I don't deploy till I've slowed till about 300m/s though and, as mentioned in the original post, it works fine on the console that way. As I start getting bigger, I start deploying the chutes at the "proper" time.
@Harry Rhodan Sorry for the confusing wording, I meant the parachute's stage 1 deployment (minimal deployment), not the rocket's. The staging for the rocket is set correctly and at the very start, the de-coupler is not unlocked, so there is no option but to bring back the flea and capsule in one piece. Nonetheless, the mk 16 chute should be able to handle it easily.
@Gargamel As mentioned in my response to Hebaru, for this particular instance, I wanted it to add additional drag. They are not deployed while until after the rocket has burned out and the speed reduced to under 300m/s (the extra drag reduces the max altitude from ~23km to ~21km). I only set the deploy altitude to max as it I wanted it to open and slow the craft before it got ripped off, so sooner the better (I started with it at the default).
That said, I found the problem and its neither the parachute nor when I'm deploying it. Turns out, for such a short jump, I didn't bother using SAS, which means after reaching max altitude, it would roll over to flying nose first and produce less drag than coming down engine first. Trying this a few times shows that the speed difference is minimal, but apparently enough, because coming down nose first fails every time, engine first works every time (I did try deploying on the way up and down, max/default chute altitude,etc, and it always worked as long as the engine was at the bottom).
Thanks all for the replies and suggestions, without them, I wouldn't have noticed the attitude issue.