start big to make it better quality
Nonsense. There's no such thing as 'sub-pixel detail'. Working in higher resolutions may be easier if you're going to use it later on on that resolution, but it doesn't add any more detail to the final version. Actually, it's more likely small details will get lost, leaving you with a less-than-desired result.
Wally allows you to drag and drop files into it (rather, into the .wad's field within Wally, so to say) and it will automatically convert these files to 8bits with as little quality-loss as possible.
Anyway, creating good textures is a long process that may take quite some time to get a hold on. Photographs are no magical texture-makers, sometimes creating ones from scratch gives a better result (though 'better' really depends on the style you're going for, hand-made ones are often more cartoony, which isn't a bad thing if you're going for that). If you are going to use photographs as a base, you'll often still need to rework them quite some. Try taking pictures without large lighting differences on the surfaces to make your job easier.
Whatever approach you're going for, use other pictures as reference. It often helps a lot. It's also a good idea to test your textures in the situations they will be used (think about lighting, especially the light color as this affects the outcome of a texture quite radically sometimes).
As for tools, Photoshop seems to be a good choice for most, but as sm0k3y said, if you're familiar with other tools it may be better to keep using them. For example, I use a combination of Paint, IPhoto Plus, Paint Shop Pro and some other tools since that's what I'm familiar with and each program is usefull in a different stage of the process.