Just to get an idea as to what the scope of effort is here, just to *replace* every piece of art in the game right now would mean creating over 1,200 new pieces of art. Since we'd be talking about animating large portions of this, I suspect the total effort would roughly triple. Now, granted, some of this we get to stretch out thanks to the magic of palette-swapping, but it's still a tremendous undertaking.
I'm always willing to compensate for solid work, ranging from in-game exclusive stuff to Gold right up through cash or whatever; we can discuss specific terms via email or PM. However, would I be able to come up with the ~15k-20k Euro to pay for all of this new artwork directly? Probably not unless the game really starts to take off, so please keep that in mind with regards to compensation. It's a pretty hideous chicken-and-egg situation, but I'm unwilling to give up ownership of the project to secure that startup capital (which is what would happen), so slow improvements until it takes off is the best I can do right now. So, with that out of the way...
I'd recommend starting a thread in 'Fan Stuff' for the initial concept ideas so existing players can chime in, too. If you want to bounce some ideas off me first so we ensure we're in the right ballpark first before opening it up to the community at large, I'm cool with that, too. All depends on where in the process you want feedback from the rest of the PQ players.

For what to start on, there are a handful of different pieces that are required, so probably we should just do the smallest amount possible for each piece so we can make sure it all fits together and can hammer out styling.
First, some high-level decisions and notes:
* GIF vs. PNG: If we do .gif, we get a more authentic old-school feel. If we do .png, we can do some subtle alpha-blending with shadows and semi-transparency. There's no real technical advantage of one over the other.
* Tilesheet vs. self-contained for animation: Tilesheets will be eminently more scalable long-term, so I'm willing to put in the programming work to make tilesheets happen.
* Color palette: This should be determined early on, so that we don't have to go back and make changes to existing artwork due to changes here. I picture PQ as colorful, moderately cartoonish, and with an emphasis on gemtones. In any event, the palette should definitely be fairly limited in order to more fully emphasize the old-school feel, as well as to reduce the chance of color mismatches once the environment is put together. No more than 128 distinct colors in the palette! (For reference, the current palette has 114 colors).
* Palette-swappable: Because of how artwork is structured right now, I have a simple Photoshop action recorded that will generate 6 variants on whatever I give it. For example, this enables me to take a single slime and turn it into 6 color variants very easily. More importantly than stretching the artwork budget, however, is that palette-swapped monsters and items are part of the "joke"... an homage to the old 8-bit RPGs where this was required due to hardware constraints.

* Animation style / number of frames /etc.: Each art component (listed later) can have its own number of frames / animation behavior as appropriate, and different animation 'behaviors' might be different, too. However, things are easier the more consistent animations are. For example, while you might have a 4-frame walking animation and a 2-frame 'idling-in-combat' animation, it would be best to avoid mixing a 2-frame house animation with a 7-frame rotating windmill since they both need to be composited together into the same scene. (This can be worked around by doubling frames where possible, but it's good to keep in mind in advance).
Artwork components of the game are (with some suggestions on where to start):
* Background tile: 32x32. Some tiles might be animated, such as grass swaying in the wind or waves of water. In any event, these should be seamlessly tileable. Recommend: grass tile or tiles.
* Background decoration: 32x32. Might start life as a larger item that we just slice up into 32x32 pieces afterwards. This would be things like houses, trees, shelves, tables, etc. Some tiles might be animated. Should be as self-contained to 32x32 blocks as is possible. Recommend: something simple like flowers or trees to help flesh out a sample scene.
* Terrain edging: 32x32. This is a special case of the background decorations, but involves transitions from one tile type to another. This one is a PITA to set up well, since it actually involves a large number of tiny pieces that get put together to make edging work 'universally'. Recommend: skip this for now; we can come back to this once more important stylistic points are hammered out.
* In-game avatar: 32x32. This will need animation to walk in the 4 cardinal directions, as well as attack, skill use, and "taking damage" animations at a minimum. It's layered up at the programming level to enable clothing customization. This means we'll need a base body that animates in all these ways, as well as individual clothing pieces that animate properly, too. Recommend: base body (male or female) with underwear built-in. Also, a separate shirt layer, animated so that it's seamless when composited together. Pants, too, if you've got time.

Probably start with a static version, and we can add animation later.
* Character detail: 64x128. This is, in effect, a larger version of the character avatar, used to help showcase character clothing. It's also layered, but probably doesn't need to be animated (though some sort of idling animation might not be a bad thing, just to make it more visually interesting). Recommend: match the in-game avatar (base body + shirt + pants)
* Monsters: 32x32. Might start life as a larger piece that gets split up into 32x32 blocks. Will need animations for: idling in combat, attacking, using skills, and taking damage (at a minimum). Recommend: the eponymous green slime, since this little guy's pretty central to the game, I think.

At first just static; we can add animations after style is hammered out.
* Inventory item: 32x32. This is the icon in the inventory or quickbar. Generally, these are size-scale independent, meaning that you mainly just fill up the 32x32 space regardless of how big or small the item would actually be. Might be animated in special cases, but would largely be static I expect. Recommend: two or three items of your choosing to help get an idea as to what these might look like.
* Skill icon: 16x16. This is a small icon to represent a given skill. Recommend: skip for now.
* Other UI elements: varies. Windows, backgrounds, menu elements, etc. Recommend: skip for now.
* Other in-game elements: varies. Might include special effects for skill/item usage, damage numbers / effects, etc. Recommend: skip for now.
Once you've got pieces from the above, I'd recommend putting together a small sample scene so we can get a good idea as to what the game might look like before getting too committed to a given style. Doesn't have to be as big as the existing map, but should be big enough to see multiple elements on the same screen, intermingling the way they might in the game. It doesn't even have to be animated to begin with - once we've proven the concept behind the new style, we can add that to the sample scene later.
As for modifying existing artwork, I'm the full owner of PQ's art, so we can do whatever we like with it. Within the context of making new art for PQ, I'm fine with using it as a starting point.
Finally, as for programming help, PQ's internals are in a pretty bad state of flux right now while I clean up a lot of older stuff and try to finalize the break from its initial implementation as a purely server-side beast, so it's not in a good state to bring other programmers into the mix. That said, the best way to help out on the programming side would be to use something like Greasemonkey or Opera's User JavaScript to modify the behavior of PQ in some new way and then show off that script. That way, you don't need me involved at all, and can get a feel for how the code works on the client side.