the easiest program I used was Milkshape, it is a bare bones program that you had to do everything in to make a model and apply the textures with.
it was also the most manual no auto tools, and the most feature limited of the the three.
GMax is simular to 3DMax and can do most of the items but I found it harder to use, simple things in Milkshape are much more complex to do. On the plus side GMax exports to the other Trek games if I remember correctly. As it is Free and is more like 3DMax it would probably be the best choice, especially if you are planning on moving up to Max, Lightwave, or the other professional programs in the future.
Industry standard is PhotoShop for lots of graphical work and expensive (700+ USD). I use PaintShop Pro version 8.1 (50 USD) at home and would not use a version above 9, which is when Corel bought them and dumbed it down to a photo editor to push there draw product. I use version 8 and Wicked Zombie uses version 6 or 7. It is pretty easy to use and can handle most of the work for games that are old like this one. For the newer games you will have to eventually move up to PhototShop, which has some differences but they are still close enough to make the change to the more expensive one.
You can try E-bay and such for the older version of these programs except 3DMax, the licence on Max once installed doesn't transfer to a new user, on of the complaints about Max ppl have had. They might have fixed this but not sure for the older versions.
There are other means to get programs for a lesser rate but you will not find those from me, but I am sure you probably know of place or two that can help
So summary:
Get GMax as it is Free and is closer, interface wise, to the professional programs used out there.
Check EBay and other software sites for older versions of PSP and PS. PSP versions 6-8 work well for older games, and PhotoShop is the industry standard
most of the things I think are covered
here