To the best of my knowledge, nothing in canon or Legends tells us exactly where a droid's personality comes from. Therefore I will provide an educated guess.
We see in Episode II that C-3PO's head was placed on a battle droid's body and a battle droid's head placed on C-3PO's head. There is clearly a personality conflict between C-3PO and the battle droid: the one with C-3PO's head fires its blaster at the Jedi and exclaims (in the battle droid's voice!) "Die, Jedi, die!", and then C-3PO apologizes in his own voice. Here's a video of the scene on Youtube:
From this scene it is apparent that a droid's personality is not entirely dependent on the verbobrain in its head. This information, combined with the fact that C-3PO was constructed out of protocol droid parts Anakin salvaged on Tatooine, indicates that C-3PO's unusual personality is likely affected by odd interactions between some of his salvaged components. A memory wipe to C-3PO's verbobrain would not totally remove his personality since his personality is evidently controlled somewhat by his other salvaged components.
On the one hand, C-3PO's personality is mostly like that of a protocol droid since he was originally manufactured as a standard protocol droid. Putting a protocol droid in stressful, violent situations (as we often see him in the movies) would reasonably cause that protocol droid's personality to be fussy and certainly worry-prone. This is simply because protocol droids would be designed to operate in non-violent situations (like negotiations) and would be very sensitive to the emotional state of individuals around it. If those individuals are stressed and worried because they are in battle then so would the protocol droid.
On the other hand, C-3PO is no ordinary protocol droid since he was salvaged from components from multiple droids. In that sense he has a unique personality that is mostly like a regular protocol droid's but particularly quirky.
In summary: As a protocol droid, C-3PO's baseline personality would likely already be somewhat fussy and worry-prone in the stressful, violent situations we often see him in. But C-3PO is no ordinary protocol droid in that he is composed of components salvaged from multiple droids, giving him an unusual personality that can't entirely be deleted by a memory wipe.