The biggest problem you're going to run into is that every technique you add to improve image quality will increase the computational cost of the program by a lot more than you'd initially expect. I'll run down a list of techniques you might want to consider by also point out their complexity and cost. All of these techniques fall under the category of Distributed Ray Tracing, which is covered in this research paper.
Soft Shadows - The idea behind soft shadows is to capture the umbra and penumbra cast by an object being illuminated by an area light source. The umbra is the portion of geometry that is completely occluded from light, and the penumbra is the area that some of the light reaches, but not all. The usual shadow technique for ray tracing is to just cast one ray towards the light source, and, if it is occluded, then the origin of that ray can be darkened appropriately. For soft shadows, instead of firing one ray, we fire multiple rays, but each to a random point on the light source. Some of them may hit, and some may be occluded. The final blended result will give either a fully-darkened or partially-lit result. Unfortunately, to get smooth results, I've found that 50 or more shadow rays have to be cast.
Glossy Surfaces - Many basic ray tracers render either completely diffuse or completely reflective surfaces. Glossy surfaces are those which are mostly diffuse by somewhat reflective. The appearance is generated by tracing multiple random rays in the cone of the reflected ray, and blending the results. The angle of the cone is determined by the roughness of the surface. Like soft shadows, many rays have to be traced in order to get smooth results, and there is a great increase in complexity here, because these rays are being traced rather than just cast.
Anti-Aliasing - In order to smooth the hard pixel edges on the final visualization of your scene, you can trace multiple rays through each pixel. Determining the points on the pixel through which the rays will be traced is an area to explore for optimizing how many rays you must trace to get a good image. You could look into something called stratified sampling.
Participating Media - This encompasses fog and dust in the scene that you're ray tracing. It can yield results like a beam of light shining in through a window. To render participating media, you have to use a technique called ray marching. You sample your ray at increments as it's sent into the scene (this sampling is saying "if I just happened to hit a spec of dust, what color would I be?"). At each sample, you cast a shadow ray to the light source. If the point is lit, then you can add the light color to that pixel. The trick is in blending the result so that it's faint enough to still see the image behind the media. Following a common theme, this technique can get expensive because you'll end up casting many shadow rays.
There are some other techniques described in the paper I listed earlier including depth of field and motion blur.
Now, as far as acceleration structures for your ray-tracer are concerned, the best that I can recommend are spatial structure like octrees or kd-trees. You only have to test your rays against geometry which is contained in the spatial partitions it intersects as it travels through the scene. Along those lines, you could also include primitive bounding boxes around your triangle meshes, to further cut down on the number of times you must check your ray against all the triangles of a mesh (because this is the most expensive part of the whole program!).
Also, if you haven't done so already, I highly recommend including a visualization for your rays which can be viewed in a rasterized version of your scene. For example, you press 't' with your mouse hovering over a pixel, and then you can draw lines to represent each type of ray that is cast as the original one makes its way through the scene.
Finally, unless you're developing your ray tracer on the GPU and including every optimization and spatial acceleration data structure in the book, you're unfortunately not going to get it running close to real time.
Good luck :)