Definitely dense - osmium or iridium as someone already mentioned. This is because buoyancy is a factor. In a vacuum, this wouldn’t matter.
Foil shapes, such as NACA foils, teardrops, etc., are good for minimizing drag, but are only effective if they maintain a stable attitude within the airflow. If you drop a shape like this, it won’t necessarily remain oriented the same way, without the addition of stabilizing fins or some other mechanism, as you would see in such streamlined projectiles as rockets, bombs and lawn darts. The addition of such appendages will create some additional drag, the magnitude of which is further dependent on the shape of the fin, etc.
For an object which can not be guaranteed to maintain attitude, there are other methods of reducing drag. One common example of this is the golf ball. If you look at fluid flow over a plain sphere, you will notice the flow split from the stagnation point at the leading end, flowing smoothly around the ball, until the flow separates a little bit behind the midpoint of the ball. Behind this flow separation exists turbulent flow (and flow reversal), acting to increase drag. With the addition of dimples, the surface roughness acts to move the separation point further back on the ball, such that if you looked at the flow from behind, the turbulent area would be a much smaller circle than you would see on a plain sphere.
At a guess, I would say that a NACA foil solid-of-revolution with small, foil profiled stabilizing fins at the trailing end, made from an extremely dense alloy, would be the fastest possible free-falling object.
As for its actual speed, terminal velocity occurs when the drag force (or other external forces) on an object produces an acceleration on that object equal and opposite to that of gravity (nominally 9.81 m/s^2 at sea level). When you take the air out of the equation, the only limit as to the speed that can be reached is the height from which the object is dropped, which is limited by the distance at which the earth’s gravity well is comparable to gravity produced by other objects such as the sun and moon. In actuality, we can’t ignore the air - all we can do is limit the effect of air resistance, but the maximum terminal velocity is dependent on factors such as fluid density, diameter of the falling object, object shape, surface roughness, fluid viscosity (temperature dependent), and so forth, not to mention that once compressibility comes into play (velocity approaching about Mach 0.3 or so), additional energy is lost, and resistance increases phenominally at Mach 1.0 due to the buildup of the sonic pressure wave (sonic boom).