I want to walk on clouds...

[TheRinni]

I'd like to have a character who can walk on clouds, though I may settle for just water.

The DC is a 120 Balance check for clouds, and 90 for liquids.

What is the best/quickest way to bump up this skill? And what is the earliest possible level I could achieve this at?

[Rogue Shadows]

You can achieve it as early as ECL 11 if you convince your DM to let you roll up a silver dragon wyrmling.

If you specifically want to do it via Balance checks, though...

[Zaq]

If you like Oriental Adventures, Blade Dancer (PrC) has absurd prereqs, but it gets a +10 competence bonus to Balance (and Jump and Tumble) at 1st, +20 at 5th, and +30 at 10th.

The Acrobat Boots soulmeld (MoI) give a +2 insight bonus on Balance (and others), +2 more per essentia. How much essentia you have and how much you can put into any one meld depends on your level and how deeply you delve into Incarnum, but assuming that you can grab the essentia from race and feats, even someone with no meldshaper levels can put in 1 essentia at level 1, 2 at level 6, 3 at level 12, and 4 at level 18.

Of course, if you want truly absurd checks, the Artificer is your best friend. They have an infusion that lets you change the bonus type granted by a magic item . . . so suddenly your five items that give competence bonuses instead give an alchemical bonus, a morale bonus, a luck bonus, a circumstance bonus, and a racial bonus. All of which now stack.

Leaps and Bounds (a Warlock invocation) can get you a +6 untyped bonus to Balance (and, once again, to Tumble and Jump) with a single dip.

[dextercorvia]

Here are some to get you started.

Item Familiar (UA) +ranks/3
Exemplar (CAdv) (or others) Take 10
Guidance of the Avatar -- Cleric1 spell (Spc) +20
Marshal (Mini) +Cha to dex based checks.

Edit: Dragonborn (Wings) gets another +10