Advice for a mathematician trying to present a paper at a CS conference?
First and foremost, stay on time. 

Usually, at conferences you are supposed to talk for a very limited amount of time, e.g. 25 minutes including 5 for questions. In such slot you will not be able to go deep into the technical details.

You should have a more "marketing" approach to presenting a paper. You have to convince the attendants about:


what your main results are
why your results are important
why later on one should spend some time to actually read your paper


Try to be simple and direct. Most attendees will also have spent part of their mental energy on previous presentations. Chances are they will forget about your paper very soon (there are too many to remember for a human mind!). Your goal is to make them to remember something about your paper.

Leave the proofs out. You can briefly mention the proof technique if relevant, though ("by reduction to problem XYZ").
Provide the definitions and statements -- if they are very technical, you can be a bit vague ("under some regularity conditions..."). Clarity trumps precision here. Provide some background for people not in the field, but do not waste time in reviewing basic definitions. Here it is important to know what the audience is familiar with, which depends on the venue. E.g. in a TCS conference, everyone knows what a non-deterministic Turing machine is.

Write and use a few (computer) slides -- you can't waste time writing on a blackboard, and most venues will expect you to have a computer presentation ready. Bring your laptop to the presentation. For a 25 minutes talk, use around 20 slides. Beforehand, make a pretend presentation in your office, and use a timer to check you can do it on time. Optionally, you can take some notes about what to say on each slide, and use these notes during the talk.

Sum up the main points in the last slide to help people remember your talk.

Expect at least a question at the end. Sometimes a question can be not very relevant since the audience may not have grasped everything. Politely answer that anyway.

The goal of the 3-pages short abstract is similar: to convince people that your results are interesting, and that they should read the full version. Try to summarize the main points, trying to convey the general idea even if the space does not allow a proper discussion. Avoid the technical parts which are not needed to assess your results.