Check the timestamps of different events in the log of Tomcat startup - although Tomcat is a little slow to start, 60s sounds like a lot. Do you have many/large applications deployed on the Tomcat instance?
For the best IDE, it is a matter of preference. If you are using Maven and don’t need the Visual Designer, NetBeans is a good option.
Jetty and recent versions of JBoss/Wildfly might start faster than Tomcat, GlassFish might also be fast. Jetty 6 starts in a blink of an eye, but doesn’t support Servlet 3.0 so you need a web.xml, and does not support modern push mechanisms. If you want to reduce the need of servlet container restarts, you could take a look at a commercial product called JRebel by the company ZeroTurnaround.
Memory leaks are most likely in the application - a memory profiler would help find them, or you can use the free tool JVisualVM that comes with the JDK to take and compare/analyze heap dumps. Commercial products tend to give more information and control over memory profiling if you have a tricky case.