As per the rules, those doing the surprise attack start on hold. Does this mean they need to also win an agility test with the non surprised character with the highest initative to actually go first?
All of the "surprising" characters may choose to go first, or choose to hold until after any other characters' action. They only need to make an opposed Agility test if they choose to interrupt a characters' action after it has started. An example of this is if an on-hold character wants to shoot the first opponent that draws a weapon, he doesn't know which opponent to target until after the opponent's turn starts.
As GM, you control the game. Just because Player B knows his card is immediately after Player A's doesn't mean your on-hold characters have to respect that.
This is the way I would play this.
A player on hold does not get a card and can act at any point. If they wanted to be first, the only time they would need the agility roll would be if the player with the highest card had an Ace of Spades as this is the highest possible card (barring a Joker - if this was the highest card then the card holder would get to go first without needing an agility roll). If the highest card was lower then there would be 'space' before then for the player on hold to go, without needing a roll.
The reason I do it this way is because this is the way going on hold and carrying your dealt card over from one round to the next works.