I can't say I remember my first fight against him... but I'd recommend really working on a couple Jobs.
However, because of his way of fighting with counters, it's not too hard to beat if you just predict his actions right. I've had battles where I took almost no damage from him, just because he never attacked.
Right off, you should have been working on Noruende Village, and hopefully maxed it all ASAP. If so, get farming money (Mechant ability doesn't stack with itself, but helps A LOT), and buy the Golden Egg (or whatever it's called), to double your money earnings (stacks with Merchant's ability), but negates Exp/JP earnings. Then, get enough to buy the Grow Egg, which will double your Exp/JP, but negate money earnings (stacks with the +10% JP ability, so bosses will give easily huge Exp and likely 999 JP (JP earn cap))
White Mage/Red Mage: Healing. You really should have gotten one either maxed or nearly so early on. -Obviously, White Mage is the better choice once you have access to Lv. 5 Magic, but otherwise, both are good, with Red giving more offensive options. Having the White Mage as sub-Job is a good idea, so you can have another Job's main Ability active. Best combo is probably Superstar, since then they can also add BP to others. Also, DEFINITELY combine the Damage Conversion ability (3SP) from Summoner, to give essentially infinite MP to the Healer. Want to run a defensive set (defense-oriented equipment, +20% HP, and the weapon should probably be Defender, as well as either the Fire/Ice Shield or whatever gives the most boost, depending on what you need.
Monk. I can't say how much I've posted about the epicness of Monk. That should already be maxed, as it gives some of the most useful survival and damage of all. -Abilities: +10%HP/+20%HP/+30%HP (This will also make surviving Susanoo EASY; just equip the two for +50% HP! Unless you are WAY underleveled... in which case, how'd you even reach it?!) Attack: PRESSURE POINT. This is the earliest super-powered attack, and may be OP, depending. I've literally beaten virtually every boss with just using that since Ch. 3. Anies and Idea both with Sub-Monk (main is whatever you're training them in), equip the S-Rank Knuckles (have NO weapon or shield on them, except maybe Knuckles, but they're usually stronger bare-handed), +10% Attack, and +30% HP for them to smash with two-Brave attacks of 9999 damage (damage cap) each almost every time and survive (end-game, they'll easily get 9000-9999HP (HP cap))
Other useful Jobs: Thief. First off, stealing Boss Items is VERY useful (some have rare and useful loot!) But, Thief also gets God-Speed Strike, which on an offensive layout can be almost as good as Pressure Point (though won't get to use twice in a turn)
Magic Swordsman (sub, always). AWESOME! Against many opponents, this is amazing! Add elemental damage to your physical attacks, further boosting them, and can add special Status effects (such as Sleep) [this also has MUCH higher chance of inflicting the status, since you'll hit far more often, and cost less, while still doing damage], or even DRAIN HP/MP (assuming you have the spells). Kind of sad, but it's usually far more useful than the actual Black/Red mage...
Valkyrie gets Jump/High Jump/Crescent Moon for some awesome damage and evasion. Just be careful to time things right, or your BP costs will get you... (also with Spirit Armor, they can take a few hits before dying, but drains their MP. Could combine with Damage Conversion maybe?)